Independent dominating sets and a second hamiltonian cycle in regular graphs (Q1386422): Difference between revisions

It is shown that every hamiltonian \(r\)-regular graph for \(r \geq 300\) has a second hamiltonian cycle. The proof uses the Lovász local lemma and a result of Carsten Thomassen that if in a hamiltonian graph \(H\) there is a set of vertices \(S\) that are independent in the hamiltonian cycle \(C\) and also dominate \(H - E(C)\), then there is a second hamiltonian cycle in \(H\). This result supports the conjecture of John Sheehan that every hamiltonian \(4\)-regular graph has a second hamiltonian cycle, since one consequence of this conjecture and other known results is that every hamiltonian \(r\)-regular graph for \(r \geq 3\) has a second hamiltonian cycle.