Few hamiltonian cycles in graphs with one or two vertex degrees

Inspired by Sheehan's conjecture that no 4 -regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles in regular graphs and nearly regular graphs. We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Exp. Math. 27 (2018), no. 4, 426-430]. Thereafter, we use the Lovasz Local Lemma to extend Thomassen's independent dominating set method. This extension allows us to find a second hamiltonian cycle that inherits linearly many edges from the first hamiltonian cycle. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen by showing that for k is an element of {5, 6} there exist infinitely many k -regular hamiltonian graphs having no independent dominating set with respect to a prescribed hamiltonian cycle. Motivated by an observation of Aldred and Thomassen, we prove that for every kappa is an element of {2, 3} and any positive integer k, there are infinitely many non -regular graphs of connectivity kappa containing exactly one hamiltonian cycle and in which every vertex has degree 3 or 2k.