Few hamiltonian cycles in graphs with one or two vertex degrees

Jan Goedgebeur, Jorik Jooken, On-Hei Solomon Lo, Ben Seamone, Carol T. Zamfirescu

Published 2022-11-15Version 1

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 [Experim. Math. 27 (2018) 426-430]. Thereafter, we use the Lov\'asz Local Lemma to extend Thomassen's independent dominating set method. 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. Motivated by an observation of Aldred and Thomassen, we prove that for every $\kappa \in \{ 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$.