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)\)”.
Reviewer: William G.Brown (Montréal)
MSC:
05C30 | Enumeration in graph theory |
05C35 | Extremal problems in graph theory |
05C45 | Eulerian and Hamiltonian graphs |
05C20 | Directed graphs (digraphs), tournaments |
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.