Hamiltonicity of planar graphs with a forbidden minor

DOI10.1002/JGT.22407zbMATH Open1409.05123arXiv1610.06558OpenAlexW2963883839WikidataQ129162842 ScholiaQ129162842MaRDI QIDQ4632017FDOQ4632017

Emily A. Marshall, Shoichi Tsuchiya, Kenta Ozeki, M. N. Ellingham

Publication date: 25 April 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

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.

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

Recommendations

• On certain Hamiltonian cycles in planar graphs
• Hamiltonicity and forbidden subgraphs in 4‐connected graphs
• Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
• On Hamilton cycles in certain planar graphs
• A generalization of Tutte's theorem on Hamiltonian cycles in planar graphs

zbMATH Keywords

Hamilton cycleplanar graphforbidden minor

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40) Graph minors (05C83)

Cited In (3)

• Minimal \(k\)-connected non-Hamiltonian graphs
• Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey

This page was built for publication: Hamiltonicity of planar graphs with a forbidden minor

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