The number of Hamiltonian decompositions of regular graphs

Roman Glebov, Zur Luria, Benny Sudakov

Published 2015-12-23Version 1

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