A computer-assisted proof of the Barnette-Goodey conjecture: not only fullerene graphs are Hamiltonian

DOI10.1137/140984737MaRDI QIDQ5208741zbMATH OpenOpenAlexWikidataFDO

Authors František Kardoš

Publication date 10 January 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonian cycleBarnette's conjecturefullerene graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Computational methods for problems pertaining to combinatorics (05-08)

Abstract: Fullerene graphs, i.e., 3-connected planar cubic graphs with pentagonal and hexagonal faces, are conjectured to be Hamiltonian. This is a special case of a conjecture of Barnette and Goodey, stating that 3-connected planar graphs with faces of size at most 6 are Hamiltonian. We prove the conjecture.

Recommendations

• Hamiltonicity of cubic planar graphs with bounded face sizes
• Hamiltonian cycles in some family of cubic 3-connected plane graphs
• Necessary condition for cubic planar 3-connected graph to be non-Hamiltonian with proof of Barnette's conjecture
• On Barnette's conjecture
• A note on Barnette's conjecture

Cites work

• scientific article; zbMATH DE number 4110708 (Why is no real title available?)
• scientific article; zbMATH DE number 3490998 (Why is no real title available?)
• scientific article; zbMATH DE number 3369404 (Why is no real title available?)
• A class of Hamiltonian polytopes
• A constructive enumeration of nanotube caps
• Catalog of all fullerenes with ten or more symmetries
• Cyclic edge-cuts in fullerene graphs
• Geometric folding algorithms. Linkages, origami, polyhedra
• Hamiltonian circuits in polytopes with even sided faces
• Long cycles in fullerene graphs
• Long cycles in fullerene graphs
• Longest cycles in generalized Buckminsterfullerene graphs
• Non-Hamiltonian simple 3-polytopes having just two types of faces
• Nonhamiltonian 3-Connected Cubic Planar Graphs
• On cyclic edge-connectivity of fullerenes
• Polyhedra of small order and their Hamiltonian properties

Cited in

(9)

• At least half of the leapfrog fullerene graphs have exponentially many Hamilton cycles
• Packing stars in fullerenes
• Matching theory and Barnette's conjecture
• Hamiltonicity of cubic planar graphs with bounded face sizes
• Hamiltonian cycles in some family of cubic 3-connected plane graphs
• Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture
• Distance-two colourings of Barnette graphs
• Zigzag Structures of Simple Two-Faced Polyhedra
• Manifolds realized as orbit spaces of non-free \(\mathbb{Z}_2^k\)-actions on real moment-angle manifolds

This page was built for publication: A computer-assisted proof of the Barnette-Goodey conjecture: not only fullerene graphs are Hamiltonian

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