2-factor Hamiltonian graphs. (Q1403914)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | 2-factor Hamiltonian graphs. |
scientific article |
Statements
2-factor Hamiltonian graphs. (English)
0 references
20 August 2003
0 references
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.
0 references
2-factor Hamiltonian graph
0 references
Heawood graph
0 references
1-factorable graph
0 references