2015/12/23 by Roman Glebov, Glebov, Roman, Zur Luria +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1512.07655
arxiv created 2016/08/29 · arxiv updated 2016/08/31
A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki's theorem from the 19th century, showing that a complete graph Kn on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r=cn for some fixed c>1/2 has a Hamiltonian decomposition, provided n=n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ)=r(1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of Kn is n(1-o(1))n2/2.