The number of Hamiltonian decompositions of regular graphs (Q1686305)

A Hamiltonian decomposition of a graph \(\Gamma\) is a decomposition of the edge set of \(\Gamma\) into Hamiltonian cycles. The classical result of Walecki says that a complete graph of odd order admits a Hamiltonian decomposition. Another well-known result due to Dirac says that a graph of order \(n\geq 3\) with minimum degree at least~\(\frac{1}{2}n\) contains a Hamiltonian cycle. Recently, \textit{D. Kühn} and \textit{D. Osthus} [J. Comb. Theory, Ser. B 104, 1--27 (2014; Zbl 1282.05084)] combined these two theorems and proved that for every real number \(c\) with \(1\geq c > \frac{1}{2}\), every \(r\)-regular graph of order~\(n\) with even degree \(r\geq cn\) admits a Hamiltonian decomposition if \(n=n(c)\) is sufficiently large. In this paper, under the same circumstances, the authors investigate the number of Hamiltonian decompositions \(H(\Gamma)\) and prove that for \(c > \frac{1}{2}\), \(H(\Gamma)=r^{\bigl(1+o(1)\bigr)rn/2}\). In the proof, they devise a nice decomposition of the edge set of a regular graph, from which they find the required number of Hamiltonian decompositions. The paper is definitely worth reading for people interested in the study of Hamiltonian decompositions.