Simple 3-polytopal graphs with edges of only two types and shortness coefficients
Simple planar 3-connected trivalent graphs are considered with only two types of faces: 5-gons and q-gons, in which no two q-gons have a common edge. For any \(q\geq 28\) infinitely many non-Hamltonian graphs are constructed. It also follows that for large enough q values any cycle in these graphs misses at least 1/60 of the vertices, thereby radically improving previous results. For all \(q\geq 16\) infinite families of graphs (not necessarily non-Hamiltonian) are constructed. It is also shown that that any graph with \(q\geq 6\) is cyclically 4-edge connected.
scientific article; zbMATH DE number 3939393