An upper bound on the shortness exponent of 1-tough, maximal planar graphs

DOI10.1016/0012-365X(91)90099-NMaRDI QIDQ805630zbMATH OpenFDO

Authors Michael B. Dillencourt

Publication date 1991

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(91)90099-N

zbMATH Keywords

1-toughmaximal planar graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

A maximal planar graph is one which triangulates the plane. A graph G is said to be 1-tough if the number of components of G-S is at most \(| S|\), for each non-empty subset S of V(G). Let h(G) denote the length of a longest cycle in G; then the shortness exponent for a class F of graphs is: \[ \sigma (F)=\liminf_{n\to \infty}\frac{\log h(G_ n)}{\log | G_ n|}, \] taken over all sequences of graphs in F for which \(| G_ n| \to \infty\). (This gives a measure of the non-hamiltonicity of F.) In this note it is shown that if F is the class of 1-tough maximal planar graphs, then \(\sigma (F)\leq \log_ 76\).

Recommendations

• On the shortness exponent of 1-tough, maximal planar graphs
• Toughness and nonhamiltonicity of polyhedral graphs
• An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs
• Non-hamiltonian 5 4-tough maximal planar graphs
• scientific article; zbMATH DE number 889955

Cites work

• A 1-tough nonhamiltonian maximal planar graph
• An upper bound on the shortness exponent of inscribable polytopes
• Graph theory
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• Recognizing tough graphs is NP-hard
• Shortness exponents of families of graphs
• Simple paths on polyhedra
• Some problems on polyhedra
• Tough graphs and Hamiltonian circuits.
• Toughness and Delaunay triangulations

Cited in

(14)

• Maximum and minimum toughness of graphs of small genus
• The complexity of recognizing tough cubic graphs
• An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs
• Toughness and Hamiltonicity of a class of planar graphs
• Non-hamiltonian 5 4-tough maximal planar graphs
• On the shortness exponent of 1-tough, maximal planar graphs
• Toughness and nonhamiltonicity of polyhedral graphs
• Toughness in graphs -- a survey
• scientific article; zbMATH DE number 1536530 (Why is no real title available?)
• scientific article; zbMATH DE number 2230266 (Why is no real title available?)
• Toughness and spanning trees in K4‐minor‐free graphs
• A construction of a 3/2-tough plane triangulation with no 2-factor
• Non-Hamiltonian 1-tough triangulations with disjoint separating triangles
• Toughness and Delaunay triangulations

This page was built for publication: An upper bound on the shortness exponent of 1-tough, maximal planar graphs

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