A lower bound for the shortness coefficient of a class of graphs
Let \(X\) be a class of graphs. The shortness coefficient \(\rho(X)\) of class \(X\) is defined as \[ \rho(X)= \liminf_{G\in X} {c(G)\over n(G)}, \] where \(c(G)\) and \(n(G)\) denote the length of a longest circuit and the number of vertices of \(G\), respectively. For a positive integer \(q\), let \(S(5,q)\) be the class of all 3-regular planar 3-connected graphs in which each face is a 5-gon or a \(q\)-gon and two \(q\)-gons do not have a boundary edge in common. In this paper, the authors prove that for \(q\geq 13\), \[ \rho(S(5,q))\geq {2\over 3}+ {(q- 6)\over 9(q- 5)}, \] which improves upon a result in \textit{P. J. Owens} [Simple 3-polytopal graphs with edges of only two types and shortness coefficients, Discrete Math. 59, 107-114 (1986; Zbl 0586.05027)].
scientific article; zbMATH DE number 612434