Can I read Few Hamiltonian Cycles in Graphs with One or Two Vertex Degrees on EtoBox?

Few Hamiltonian Cycles in Graphs with One or Two Vertex Degrees by Goedgebeur, Jan; Jooken, Jorik; Lo, On-Hei Solomon; Seamone, Ben; Zamfirescu, Carol T. is a scholarly article available to read on EtoBox.

What is Few Hamiltonian Cycles in Graphs with One or Two Vertex Degrees about?

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$.

Author

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

Published

2022

Language

EN