Few Hamiltonian cycles in graphs with one or two vertex degrees (Q6590640)

\textit{J. Sheehan} [in: Recent advances in graph theory. Proceedings of the symposium held in Prague, June 1974. Prague: Publishing House of the Czechoslovak Academy of Science. 477--480 (1975; Zbl 0327.05116)] conjectured that no Hamiltonian 4-regular graph contains exactly one Hamiltonian cycle. Motivated by this conjecture, the authors of this paper consider the number of Hamiltonian cycles in Hamiltonian \(k\)-regular and \((k,l)\)-regular graphs, that is, graphs in which every vertex has degree \(k\) or \(l\).\N\NFor example, it was conjectured by \textit{M. Haythorpe} [Exp. Math. 27, No. 4, 426--430 (2018; Zbl 1403.05082)] that for \(d \ge 5\) and \(n \ge d+3\), all Hamiltonian \(d\)-regular graphs of order \(n\) have at least\N\[ \N(d-1)^2[(d-2)!]^{n/(d+1)} \N\] \NHamiltonian cycles. Here, the authors fully disprove Haythorpe's conjecture.\N\NThe authors also use the Lovasz local lemma to extend \textit{C. Thomassen}'s independent dominating set method [J. Comb. Theory, Ser. B 72, No. 1, 104--109 (1998; Zbl 0895.05038)] to answer a question of \textit{P. Haxell} et al. [J. Graph Theory 54, No. 3, 233--244 (2007; Zbl 1112.05077)]. They show that for \(k \in \{5,6\}\), there exist infinitely many \(k\)-regular graphs with a Hamiltonian cycle \(C\) containing no \(C\)-independent dominating set.