×

Counting Hamilton decompositions of oriented graphs. (English) Zbl 1420.05143

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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 1261.05053
PDFBibTeX XMLCite
Full Text: DOI arXiv Link