Few hamiltonian cycles in graphs with one or two vertex degrees
Preprint
Abstract
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$.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- House of Graphs 2.0: A database of interesting graphs and moreDiscrete Applied Mathematics, 2022
- A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphsJournal of Heuristics, 2020
- Long cycles in Hamiltonian graphsIsrael Journal of Mathematics, 2018
- Practical graph isomorphism, IIJournal of Symbolic Computation, 2014
- Uniquely Hamiltonian Graphs of Minimum Degree 4Journal of Graph Theory, 2013
- Independent dominating sets and hamiltonian cyclesJournal of Graph Theory, 2006
- Fast generation of regular graphs and construction of cagesJournal of Graph Theory, 1999
- Independent Dominating Sets and a Second Hamiltonian Cycle in Regular GraphsJournal of Combinatorial Theory, Series B, 1998
- Chords of Longest Cycles in Cubic GraphsJournal of Combinatorial Theory, Series B, 1997
- Spanning cycles of nearly cubic graphsJournal of Combinatorial Theory, Series B, 1980