Every $r$-regular Hamiltonian graph with $r\geq 17$ contains a second Hamilton cycle

arXiv:2611.06985v1 Announce Type: new 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\geq k$. Thomassen proved that $k\leq 300$. Improving Thomassen's result, Haxell, Seamone, and Verstra{\"e}te proved that $k\leq 23$. We improve this bound by proving that every $r$-regular Hamiltonian graph contains a second Hamilton cycle whenever $r\geq 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\ge 18$, we also give some algorithms to find such a transversal.

You are being forwarded in 6s — stay on this page