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

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 ≥ 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. ii Acknowledgements I would sincerely like to thank my supervisor, Mateja Šajna, for her tireless patience and support throughout the development of this work. Her enthusiasm, sagacity, and constant optimism have been an invaluable resource, and these qualities have effected the work you see before you. Mateja, thank you for making me proud to call you m