An update on non-Hamiltonian 54-tough maximal planar graphs

DOI10.1016/J.DISC.2017.10.034MaRDI QIDQ1690216zbMATH OpenOpenAlexFDO

Authors Adam Kabela

Publication date 19 January 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

maximal planar graphsshortness exponenttoughness

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: Studying the shortness of longest cycles in maximal planar graphs, we improve the upper bound on the shortness exponent of the class of $frac54$-tough maximal planar graphs presented by Harant and Owens [Discrete Math. 147 (1995), 301--305]. In addition, we present two generalizations of a similar result of Tk'{a}v{c} who considered $1$-tough maximal planar graphs [Discrete Math. 154 (1996), 321--328]; we remark that one of these generalizations gives a tight upper bound. We fix a problematic argument used in the first paper.

Recommendations

• Non-hamiltonian 5 4-tough maximal planar graphs
• scientific article; zbMATH DE number 1536530
• scientific article; zbMATH DE number 68618
• Toughness and Hamiltonicity of a class of planar graphs
• Maximum nonhamiltonian tough graphs
• scientific article; zbMATH DE number 4101250
• Toughness and nonhamiltonicity of polyhedral graphs
• Publication:3470493
• Toughness and prism-Hamiltonicity of \(P_4\)-free graphs
• On maximal planarization of nonplanar graphs

Cites work

• A Theorem on Planar Graphs
• An upper bound on the shortness exponent of 1-tough, maximal planar graphs
• scientific article; zbMATH DE number 1536530 (Why is no real title available?)
• Long cycles in 3-connected graphs
• More than one tough chordal planar graphs are Hamiltonian
• Non-hamiltonian 5 4-tough maximal planar graphs
• Not every 2-tough graph is Hamiltonian
• On the shortness exponent of 1-tough, maximal planar graphs
• Shortness exponents of families of graphs
• Shortness parameters for polyhedral graphs
• Simple paths on polyhedra
• Tough graphs and Hamiltonian circuits.
• Toughness and nonhamiltonicity of polyhedral graphs
• Toughness in graphs -- a survey

Cited in

(5)

• Long paths and toughness of \(k\)-trees and chordal planar graphs
• Non-hamiltonian 5 4-tough maximal planar graphs
• On the shortness exponent of 1-tough, maximal planar graphs
• scientific article; zbMATH DE number 1536530 (Why is no real title available?)
• An upper bound on the shortness exponent of 1-tough, maximal planar graphs

This page was built for publication: An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs

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