Every r-regular Hamiltonian graph with r≥ 17 contains a second Hamilton cycle
Abstract
A conjecture of Sheehan states that every Hamiltonian $4$-regular graph contains a second Hamilton cycle. A natural problem is to find the smallest positive integer k such that every Hamiltonian r-regular graph contains a second Hamilton cycle when r≥ k. Thomassen proved that k≤ 300. Improving Thomassen's result, Haxell, Seamone, and Verstra{ë}te proved that k≤ 23. We improve this bound by proving that every r-regular Hamiltonian graph contains a second Hamilton cycle whenever r≥ 17. Our new idea is to establish a transversal theorem for set systems on a cycle using Harris's results on the Moser--Tardos algorithm for Local Lemma. We then apply Thomassen's theorem on independent dominating sets to obtain a second Hamilton cycle. For r≥ 18, we also give some algorithms to find such a transversal.
Related
- Every introenumerable set contains a uniformly introreducible subset
- Every Nonrecursive Many-One Degree Contains Either One or Infinitely Many Finite-One Degrees
- The realization graph of every degree sequence has a Hamilton path
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- Equivalence between Strict Viscosity Solution and Viscosity Solution in the Wasserstein Space and Regular Extension of the Hamiltonian in L 2 ℙ
BibTeX
@misc{liu2026every,
title = {{Every $r$-regular Hamiltonian graph with $r\geq 17$ contains a second Hamilton cycle}},
author = {Haiyang Liu and Xu Liu and Bo Ning},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06985},
eprint = {2611.06985},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06985},
}
RIS
TY - UNPB
TI - Every r-regular Hamiltonian graph with r≥ 17 contains a second Hamilton cycle
AU - Haiyang Liu
AU - Xu Liu
AU - Bo Ning
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06985
UR - https://arxiv.org/abs/2611.06985
AB - A conjecture of Sheehan states that every Hamiltonian $4$-regular graph contains a second Hamilton cycle. A natural problem is to find the smallest positive integer k such that every Hamiltonian r-regular graph contains a second Hamilton cycle when r≥ k. Thomassen proved that k≤ 300. Improving Thomassen's result, Haxell, Seamone, and Verstra{ë}te proved that k≤ 23. We improve this bound by proving that every r-regular Hamiltonian graph contains a second Hamilton cycle whenever r≥ 17. Our new idea is to establish a transversal theorem for set systems on a cycle using Harris's results on the Moser--Tardos algorithm for Local Lemma. We then apply Thomassen's theorem on independent dominating sets to obtain a second Hamilton cycle. For r≥ 18, we also give some algorithms to find such a transversal.
ER -