×

On the maximum number of Hamiltonian paths in tournaments. (English) Zbl 0982.05056

For a tournament \(T\) with labelled vertices, \(P(T)\) (respectively \(C(T)\)) denote the numbers of Hamiltonian paths (respectively Hamiltonian cycles); the maximum over all tournaments \(T\) having \(n\) vertices are denoted by \(T(n)\) (respectively \(C(n)\)). A lower bound of T. Szele [Kombinatorische Untersuchungen über den gerichteten vollständigen Graphen. (Hungarian. German summary). Mat. Fiz. Lapok 50, 223-256 (1943; Zbl 0061.41309)], that \(P(n)\geq\frac{n!}{2^{n-1}}\), is sharpened in Theorem 1: \(P(n)\geq(e-o(1))\frac{n!}{2^{n-1}}\) as \(n\to\infty\). A lower bound for \(C(n)\) is also investigated. It is observed that N. Alon [Combinatorica 10, No. 4, 319-324 (1990; Zbl 0724.05036)] has shown that \(P(n)\leq O(n^{\frac 32}\cdot\frac{n!}{2^n})\), and that this bound has recently been improved by E. Friedgut and J. Kahn. “It would be interesting to decide if \(P(n)=\Theta\left(\frac{n!}{2^n}\right)\)”.

MSC:

05C30 Enumeration in graph theory
05C35 Extremal problems in graph theory
05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI

References:

[1] Alon, Combinatorica 10 pp 319– (1990) · Zbl 0724.05036 · doi:10.1007/BF02128667
[2] and The probabilistic method, Wiley, New York, 2000, 2nd ed. · doi:10.1002/0471722154
[3] and in preparation.
[4] Schönheim, Studia Sci Math Hungar 1 pp 363– (1966)
[5] Szele, Mat Fiz Lapok 50 pp 223– (1943)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.