On the Existence of a Second Hamilton Cycle in Hamiltonian Graphs With Symmetry

Abstract

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.