2-factor Hamiltonian graphs.

DOI10.1016/S0095-8956(02)00031-XMaRDI QIDQ1403914zbMATH OpenFDO

Authors Bill Jackson, M. J. Funk, D. Labbate, J. Sheehan

Publication date 20 August 2003

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0095-8956(02)00031-X

zbMATH Keywords

1-factorable graph2-factor Hamiltonian graphHeawood graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Review text

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.

Recommendations

• On 2-factor Hamiltonian regular bipartite graphs
• Betwixt and between 2-factor Hamiltonian and perfect-matching-Hamiltonian graphs
• Regular bipartite graphs with all 2-factors isomorphic
• scientific article; zbMATH DE number 2192128
• Hamilton cycles in 2-connected regular bipartite graphs

Cites work

• A characterization of convertible (0,1)-matrices
• Characterizing minimally 1-factorable r-regular bipartite graphs
• Even dicycles
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• scientific article; zbMATH DE number 1985430 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• Independent dominating sets and a second hamiltonian cycle in regular graphs
• Matching theory
• On 3-cut reductions of minimally 1-factorable cubic bigraphs
• On Hamiltonian Circuits
• On minimally one-factorable r-regular bipartite graphs
• On the number of Hamiltonian cycles in bipartite graphs
• Permanents, Pfaffian orientations, and even directed circuits

Cited in

(22)

• 2-factors and Hamiltonicity
• Regular bipartite graphs with all 2-factors isomorphic
• Chords of 2-factors in planar cubic bridgeless graphs
• Superposition of snarks revisited
• On 2-factor Hamiltonian regular bipartite graphs
• A counterexample to the pseudo 2-factor isomorphic graph conjecture
• Odd 2-factored snarks
• Pseudo 2-factor isomorphic regular bipartite graphs
• A construction for a counterexample to the pseudo 2-factor isomorphic graph conjecture
• Betwixt and between 2-factor Hamiltonian and perfect-matching-Hamiltonian graphs
• An equivalent formulation of the Fan-Raspaud conjecture and related problems
• On perfectly one–factorable cubic graphs
• Irreducible pseudo 2-factor isomorphic cubic bipartite graphs
• Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs
• K₂-Hamiltonian graphs: I
• Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
• Finding matching cuts in \(H\)-free graphs
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Cubic graphs having only k-cycles in each 2-factor
• A note on the 2-factor Hamiltonicity conjecture
• Graphs and digraphs with all 2-factors isomorphic
• The Gray graph is pseudo 2-factor isomorphic

This page was built for publication: 2-factor Hamiltonian graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1403914)