Ferber, Asaf; Long, Eoin; Sudakov, Benny Counting Hamilton decompositions of oriented graphs. (English) Zbl 1420.05143 Int. Math. Res. Not. 2018, No. 22, 6908-6933 (2018). Summary: A Hamilton cycle in a directed graph \(G\) is a cycle that passes through every vertex of \(G\). A Hamilton decomposition of \(G\) is a partition of its edge set into disjoint Hamilton cycles. In the late \(60\)s, Kelly conjectured that every regular tournament has a Hamilton decomposition. This conjecture was recently settled for large tournaments by D. Kühn and D. Osthus [Adv. Math. 237, 62–146 (2013; Zbl 1261.05053)], who proved more generally that every \(r\)-regular \(n\)-vertex oriented graph \(G\) (without antiparallel edges) with \(r=cn\) for some fixed \(c>3/8\) has a Hamilton decomposition, provided \(n=n(c)\) is sufficiently large. In this article, we address the natural question of estimating the number of such decompositions of \(G\) and show that this number is \(n^{(1-o(1))cn^2}\). In addition, we also obtain a new and much simpler proof for the approximate version of Kelly’s conjecture. Cited in 3 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C45 Eulerian and Hamiltonian graphs 05C20 Directed graphs (digraphs), tournaments Keywords:tournaments; Hamilton decomposition; robust expanders; travelling salesman problem; Hamilton cycles Citations:Zbl 1261.05053 PDFBibTeX XMLCite \textit{A. Ferber} et al., Int. Math. Res. Not. 2018, No. 22, 6908--6933 (2018; Zbl 1420.05143) Full Text: DOI arXiv Link