Non-Hamiltonian 3-Connected Cubic Planar Graphs with Only Two Types of Faces besides 4-Gons

摘要

Let G(p,q,r) denote the class of all 3-connected cubic planar graphs whose faces are of only three types, namely p-gon, q-gon and r-gon. Here, we show that there exist non-hamiltonian members for the following classes of graphs: (i) G(3,4,r) for r ≥ 7, (ii) G(4,5,r) for r ≥ 8, (iii) G(4,q,r) for q ∈ {7,9,11} and r ≥ 6 and (iv) G(4, q,q + 5) and G(4, q + 2, q + 5) for q ≥ 5.