On the Existence of a Second Hamilton Cycle in Hamiltonian Graphs With Symmetry - Wagner, Andrew (Université d'Ottawa / University of Ottawa, 2013)
In 1975, Sheehan conjectured that every simple 4-regular hamiltonian graph has a second Hamilton cycle. If Sheehan's Conjecture holds, then the result can be extended to all simple d-regular hamiltonian graphs with d at least 3. First, we survey some previous results which verify the existence of a second Hamilton cycle if d is large enough. We will then demonstrate some techniques for finding a second Hamilton cycle that will be used throughout this paper. Finally, we use these techniques and show that for certain 4-regular Hamiltonian graphs whose automorphism group is large enough, a second Hamilton cycle exists.
Keywords: Hamilton cycle; regular graph; Sheehan's Conjecture; automorphism group