zbMATH — the first resource for mathematics

Edge disjoint Hamiltonian cycles in highly connected tournaments. (English) Zbl 1405.05097
Summary: C. Thomassen [Proc. Lond. Math. Soc. (3) 45, 151–168 (1982; Zbl 0486.05049)] conjectured that there is a function \(f(k)\) such that every strongly \(f(k)\)-connected tournament contains \(k\) edge-disjoint Hamiltonian cycles. This conjecture was recently proved by D. Kühn et al. [Proc. Lond. Math. Soc. (3) 109, No. 3, 733–762 (2014; Zbl 1302.05069)] who showed that \(f(k) \leq O(k^2(\log k)^2)\) and conjectured that there is a constant \(C\) such that \(f(k)\leq Ck^2\). We prove this conjecture. As a second application of our methods, we answer a question of Thomassen about spanning linkages in highly connected tournaments.

05C45 Eulerian and Hamiltonian graphs
Full Text: DOI arXiv