In 1975, Sheehan conjectured that every d-regular Hamiltonian graph contains a second Hamiltonian cycle. This conjecture has been verified for all d greater than 22. In the light of Sheehan’s conjecture, it is natural to ask if regularity is genuinely necessary to force the existence of a second Hamiltonian cycle, or if a minimum degree condition is enough. Etringer and Swart answered this question negatively by constructing infinitely many uniquely Hamiltonian graphs with minimum degree 3, however, it is still an open problem to decide if minimum degree larger than 5 forces a second Hamiltonian cycle. In this talk, we shall discuss a recent result which asserts that a Hamiltonian graph with minimum degree 3 must contain another cycle of order at least n-o(n), thus answering, in an asymptotic form the above question.
This work is joint with Kittipassorn and Narayanan.