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
    0 references
    0 references
    0 references
    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

    Identifiers