The number of Hamiltonian decompositions of regular graphs

Abstract

A Hamilton cycle in a graph $\hat{I}“$ is a cycle passing through every vertex of $\hat{I}“$. A Hamiltonian decomposition of $\hat{I}“$ 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 $K_n$ 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 $\hat{I}“$ 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(\hat{I}“)$, the number of such decompositions of $\hat{I}“$. Our main result is that $H(\hat{I}“)=r^{(1+o(1))nr/2}$. In particular, the number of Hamiltonian decompositions of $K_n$ is $n^{(1-o(1))n^2/2}$.