A nonhamiltonian five-regular multitriangular polyhedral graph (Q1916128): Difference between revisions

Let \(G\) be a polyhedral graph, i.e. \(G\) is planar and 3-connected. Then \(G\) is called multitriangular if each face of \(G\) is a \(q\)-gon for some \(q\) divisible by 3. In the present paper, the author constructs a 5-regular multitriangular graph with 1728 vertices which does not contain a Hamiltonian cycle. Moreover, he proves that the so-called shortness-exponent of the class \(\Gamma\) of all 5-regular multitriangular graphs is less than one. As a consequence, for some \(\sigma< 1\), there exist arbitrarily large members \(G\) of \(\Gamma\) such that \({\log c(G)\over \log|V(G)|}\leq \sigma\), where \(c(G)\) denotes the length of a longest cycle in \(G\).