We give constructive proofs for the existence of uniquely hamiltonian graphs for various sets of degrees. We give constructions for all sets with minimum 2 (a trivial case added for completeness), all sets with minimum 3 that contain an even number (for sets without an even number it is known that no uniquely hamiltonian graphs exist), and all sets with minimum 4, except {4}, {4,5}, and {4,6}. For minimum degree 3 and 4, the constructions also give 3-connected graphs. We also introduce the concept of seeds, which makes the above results possible and might be useful in the study of Sheehan's conjecture. Furthermore, we prove that 3-connected uniquely hamiltonian 4-regular graphs exist if and only if 2-connected uniquely hamiltonian 4-regular graphs exist.
Discrete Mathematics & Theoretical Computer Science