Longest cycles in polyhedral graphs (Q690053)

For a graph \(G\), let \(\nu(G)\) and \(c(G)\) be the number of vertices and the circumference of \(G\), respectively. If \(\Gamma\) is a family of graphs, the shortness exponent of \(\Gamma\), \(\sigma(\Gamma)\), is defined as \[ \sigma(\Gamma):=\liminf_{G\in \Gamma}{\log c(G)\over\log\nu(G)}. \] Several families of polyhedral graphs \(\Gamma\) are known such that \(\sigma(\Gamma)<1\) and \(\sigma(\Gamma^*)<1\),where \(\Gamma^*=\{G^*\mid G\) is in \(\Gamma\) and \(G^*\) is dual to \(G\}\). Constructed is a sequence \(\{G_ n\}\) of polyhedral graphs having only vertices of degree 3 and 8 and only triangles and octagons as faces such that \(\sigma(\{G_ n\})<1\) and \(\sigma(\{G^*_ n\})<1\). The construction starts with a certain non-Hamiltonian graph \(G_ 1\) on 14 vertices. It proceeds by a process of replacing each 3-valent vertex by a modified \(G_ 1\).