Hamiltonicity of planar graphs with a forbidden minor

DOI10.1002/JGT.22407MaRDI QIDQ4632017zbMATH OpenOpenAlexWikidataFDO

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

Publication date 25 April 2019

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

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

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)

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.

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

Cited in

(5)

• \(K_2\)-Hamiltonian graphs: I
• A characterization of \(K_{2,4}\)-minor-free graphs
• 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)