Hamiltonicity of planar graphs with a forbidden minor

2016/10/20 by M. N. Ellingham, Ellingham, M. N., Emily A. Marshall +5 · 1 citation
Computer Science · #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1610.06558

openalex publication_date 2016/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Tutte showed that 4-connected planar graphs are Hamiltonian, but it is well known that 3-connected planar graphs need not be Hamiltonian. We show that K_2,5-minor-free 3-connected planar graphs are Hamiltonian. This does not extend to K_2,5-minor-free 3-connected graphs in general, as shown by the Petersen graph, and does not extend to K_2,6-minor-free 3-connected planar graphs, as we show by an infinite family of examples.

Cited by

• Minors of non-hamiltonian polyhedra and the Herschel family

Related

• On minors of non-hamiltonian graphs
• On planar regular graphs degree three without Hamiltonian cycles
• 4-connected 1-planar chordal graphs are Hamiltonian-connected
• Are highly connected 1-planar graphs Hamiltonian?
• A characterization of K_2,4-minor-free graphs