Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of Barnette's Conjecture

Abstract

We study the existence of hamiltonian cycles in plane cubic graphs 𝐺 having a facial 2-factor Q. Thus hamiltonicity in 𝐺 is transformed into the existence of a (quasi) spanning tree of faces in the contraction 𝐺∕Q. In particular, we study the case where 𝐺 is the leapfrog extension (called vertex envelope of a plane cubic graph 𝐺₀. As a consequence we prove hamiltonicity in the leapfrog extension of planar cubic cyclically 4-edge-connected bipartite graphs. This and other results of this paper establish partial solutions of Barnette's Conjecture according to which every 3-connected cubic planar bipartite graph is hamiltonian. These results go considerably beyond Goodey's result on this topic.