The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices

DOI10.1016/0095-8956(88)90075-5zbMath0607.05051DBLPjournals/jct/HoltonM88OpenAlexW2051837347WikidataQ55933544 ScholiaQ55933544MaRDI QIDQ1085184

Derek Holton, Brendan D. McKay

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0095-8956(88)90075-5

zbMATH Keywords

convex polytopeHamiltonian cyclecubic planar graphsnon-Hamiltonian graphsimplex polytope

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Length, area and volume in real or complex geometry (51M25) Eulerian and Hamiltonian graphs (05C45) Polytopes and polyhedra (52Bxx)

Related Items (25)

Grinberg's criterion ⋮ The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices ⋮ Cycles in 4-connected planar graphs ⋮ Pentagonal 3-polytopal graphs with edges of only two types and shortness parameters ⋮ Cuts in matchings of 3-connected cubic graphs ⋮ The minimality of the Georges–Kelmans graph ⋮ The circumference of a graph with no \(K_{3,t}\)-minor ⋮ Structural and computational results on platypus graphs ⋮ On the shortness exponent of 1-tough, maximal planar graphs ⋮ On the circumference of 3-connected cubic triangle-free plane graphs ⋮ Upper Bound Constructions for Untangling Planar Geometric Graphs ⋮ Hamiltonian tetrahedralizations with Steiner points ⋮ Improved bounds for hypohamiltonian graphs ⋮ Distance-two colourings of Barnette graphs ⋮ On the 4-color theorem for signed graphs ⋮ Small \(k\)-pyramids and the complexity of determining \(k\) ⋮ A note on 3-connected cubic planar graphs ⋮ Hamiltonian properties of polyhedra with few 3-cuts. A survey ⋮ A note on the smallest connected non-traceable cubic bipartite planar graph ⋮ Structure and pancyclicity of maximal planar graphs with diameter two ⋮ On the minimum leaf number of cubic graphs ⋮ On Hypohamiltonian and Almost Hypohamiltonian Graphs ⋮ Regular non-Hamiltonian polyhedral graphs ⋮ Long cycles in 3-connected graphs ⋮ Tutte paths and long cycles in circuit graphs

Uses Software

• nauty

Cites Work

• Non-Hamiltonian cubic planar maps
• Every simple 3-polytype with 34 vertices is Hamiltonian
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• Hamiltonian circuits on simple 3-polytopes with up to 30 vertices
• Hamiltonian circuits in simple 3-polytopes with up to 26 vertices
• Hamiltonian circuits on simple 3-polytopes
• Every simple 3-polytope of order 32 or less is Hamiltonian
• Hamilton Circuits of Convex Trivalent Polyhedra (Up to 18 Vertices)
• Polytopes, graphs, and complexes
• Hamiltonian Circuits on Simple 3-Polytopes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices