The minimality of the Georges-Kelmans graph

DOI10.1090/MCOM/3701MaRDI QIDQ5070550zbMATH OpenOpenAlexFDO

Authors Gunnar Brinkmann, Jan Goedgebeur, Brendan D. McKay

Publication date 13 April 2022

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.00943

zbMATH Keywords

Barnette's conjecturebipartiteconnectivitycubicgenusHamiltonian cycleTutte's conjecture

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: In 1971, Tutte wrote in an article that "it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian". Motivated by this remark, Horton constructed a counterexample on 96 vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts -- even if they have girth 6 -- it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs. In 1969, Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnette's conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than 4.

Recommendations

• Hamiltonian cycles in cubic 3-connected bipartite planar graphs
• scientific article; zbMATH DE number 634025
• scientific article; zbMATH DE number 6029
• Construction of Barnette graphs whose large subgraphs are non-Hamiltonian
• Non-Hamiltonian bicubic graphs

Cites work

• Cubic bipartite cyclic 4-connected graphs without Hamiltonian circuits
• Cuts in matchings of 3-connected cubic graphs
• Edge reductions in cyclically \(k\)-connected cubic graphs
• Fast generation of cubic graphs
• Fast generation of planar graphs
• Fast generation of regular graphs and construction of cages
• Graph theory
• Graph theory with applications
• Hamiltonian cycles in cubic 3-connected bipartite planar graphs
• House of Graphs: a database of interesting graphs
• scientific article; zbMATH DE number 446400 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 558005 (Why is no real title available?)
• scientific article; zbMATH DE number 3305794 (Why is no real title available?)
• Non-Hamiltonian 3-connected cubic bipartite graphs
• Non-Hamiltonian bicubic graphs
• On Hamiltonian Circuits
• On the 2-factors of bicubic graphs
• On two-factors of bipartite regular graphs
• Practical graph isomorphism. II.
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices

Cited in

(9)

• Matching theory and Barnette's conjecture
• scientific article; zbMATH DE number 634025 (Why is no real title available?)
• scientific article; zbMATH DE number 1471086 (Why is no real title available?)
• scientific article; zbMATH DE number 6029 (Why is no real title available?)
• Nonhamiltonian 3-Connected Cubic Planar Graphs
• K₂‐Hamiltonian graphs: II
• A sufficient condition for cubic 3-connected plane bipartite graphs to be Hamiltonian
• The Gray graph is pseudo 2-factor isomorphic
• Approximating Barnette's conjecture

Describes a project that uses

Uses Software

• nauty
• plantri
• Traces
• House of Graphs
• GENREG

This page was built for publication: The minimality of the Georges-Kelmans graph

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