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

DOI10.1137/140984737zbMATH Open1430.05022arXiv1409.2440OpenAlexW2998814501WikidataQ123248360 ScholiaQ123248360MaRDI QIDQ5208741FDOQ5208741

František Kardoš

Publication date: 10 January 2020

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

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.

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

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

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)

Cites Work

• Hamiltonian circuits in polytopes with even sided faces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cyclic edge-cuts in fullerene graphs
• On cyclic edge-connectivity of fullerenes
• A class of Hamiltonian polytopes
• A constructive enumeration of nanotube caps
• Title not available (Why is that?)
• Nonhamiltonian 3-Connected Cubic Planar Graphs
• Non-Hamiltonian simple 3-polytopes having just two types of faces
• Title not available (Why is that?)
• Long cycles in fullerene graphs
• Long cycles in fullerene graphs
• Longest cycles in generalized Buckminsterfullerene graphs
• Polyhedra of small order and their Hamiltonian properties

Cited In (8)

• Packing stars in fullerenes
• Distance-two colourings of Barnette graphs
• At least half of the leapfrog fullerene graphs have exponentially many Hamilton cycles
• 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
• Manifolds realized as orbit spaces of non-free \(\mathbb{Z}_2^k\)-actions on real moment-angle manifolds
• Matching theory and Barnette's conjecture
• Zigzag Structures of Simple Two-Faced Polyhedra

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)