Abstract
Let P(n) and C(n) denote, respectively, the maximum possible numbers of Hamiltonian paths and Hamiltonian cycles in a tournament on n vertices. The study of P(n) was suggested by Szele [14], who showed in an early application of the probabilistic method that P(n) ≥ n!2-n+1, and conjectured that lim(P(n)/n!)1/n= 1/2. This was proved by Alon [2], who observed that the conjecture follows from a suitable bound on C(n), and showed C(n) Here we improve this to C(n) with ξ = 0.2507... Our approach is mainly based on entropy considerations.
Original language | English (US) |
---|---|
Pages (from-to) | 769-781 |
Number of pages | 13 |
Journal | Combinatorics Probability and Computing |
Volume | 14 |
Issue number | 5-6 |
DOIs | |
State | Published - Nov 2005 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics