2-factor Hamiltonian graphs. (Q1403914)

A graph \(G\) is called 2-factor Hamiltonian if all 2-factors of \(G\) are Hamiltonian. \(K_{3,3}\) and the Heawood graph are examples of cubic bipartite 2-factor Hamiltonian graphs. As the star product of two bipartite 2-factor Hamiltonian graphs is again 2-factor Hamiltonian, there exists an infinite family of cubic bipartite 2-factor Hamiltonian graphs. The authors prove that \(k\)-regular 2-factor Hamiltonian graphs exist only for \( k=2\) and \(k=3\). They conjecture that all nontrivial regular 2-factor Hamiltonian graphs are iterated star products of \(K_{3,3}\) and the Heawood graph.