| Abstract: | We construct a small non-Hamiltonian 3-connected trivalent planar graph whose faces are all 4-gons or 7-gons and show that the shortness coefficient of the class of such graphs is less than one. Then, by transforming non-Hamiltonian trivalent graphs into regular graphs of valency four or five, we obtain our main results, as follows. We show first that the class of 3-connected r-valent planar graphs whose faces are of only two types, triangles and q-gons, contains non-Hamiltonian members and has a shortness exponent less than one when r = 4, for all q ≧ 12. Under the extra restriction that, among graphs of connectivity three, only those with maximum cyclic edge-connectivity are to be considered, we prove the same result also when r = 4, for q = 20, and when r = 5, for all q ≧ 14 except multiples of three. |
