A lower bound on the number of hamiltonian cycles (Q1579572)

\textit{C. Thomassen} [J. Comb. Theory, Ser. B 72, No. 1, 104-109 (1998; Zbl 0895.05038)] showed that any \(r\)-regular hamiltonian graph, \(r\geq 300\), has a second hamiltonian cycle. Refining his methods the authors prove: Let \(G\) be a hamiltonian graph. \(\Delta\) and \(\delta\) be its maximum and minimum degree, respectively. Then for any real number \(k\geq 1\) there exists \(\Delta(k)\) so that \(G\) has at least \(\delta-\lfloor \Delta/k \rfloor+2\) hamiltonian cycles if \(\Delta\geq \Delta(k)\). In particular, if \(k\geq \Delta/\delta\) and \(\Delta \geq \Delta(k)\) then \(G\) has a second hamiltonian cycle. A simple method for calculating an upper bound on \(\Delta(k)\) is given as well.