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

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\).