A note on the number of Hamiltonian paths in strong tournaments

MaRDI QIDQ813441zbMATH OpenFDO

Authors Arthur H. Busch

Publication date 9 February 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/125519, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1n3.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

Summary: We prove that the minimum number of distinct Hamiltonian paths in a strong tournament of order \(n\) is \(5^{\frac {n-1}3}\). A known construction shows this number is best possible when \(n \equiv 1 \bmod 3\) and gives similar minimal values for \(n\) congruent to 0 and 2 modulo 3.

Recommendations

• scientific article; zbMATH DE number 3977040
• scientific article; zbMATH DE number 5178703
• On the maximum number of Hamiltonian paths in tournaments
• The maximum number of Hamiltonian paths in tournaments
• About the number of oriented Hamiltonian paths and cycles in tournaments
• On the Number of Hamiltonian Cycles in a Tournament
• scientific article; zbMATH DE number 3884197
• Tight bounds for powers of Hamilton cycles in tournaments
• scientific article; zbMATH DE number 3902692

Cited in

(10)

• The maximum number of Hamiltonian paths in tournaments
• About the number of directed paths in tournaments
• On the maximum number of Hamiltonian paths in tournaments
• Non-critical vertices and long circuits in strong tournaments of order n and diameter d
• scientific article; zbMATH DE number 3977040 (Why is no real title available?)
• A survey on Hamilton cycles in directed graphs
• About the number of oriented Hamiltonian paths and cycles in tournaments
• Number of subgraphs and their converses in tournaments and new digraph polynomials
• About the number of directed Hamiltonian paths in special tournaments
• An updated survey on the linear ordering problem for weighted or unweighted tournaments

This page was built for publication: A note on the number of Hamiltonian paths in strong tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q813441)