Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture
Bagheri Gh, Behrooz, Tomás Feder, Herbert Fleischner, Carlos Subi · PubMed Central · 2020
We study the existence of hamiltonian cycles in plane cubic graphs [Formula: see text] having a facial 2‐factor [Formula: see text]. Thus hamiltonicity in [Formula: see text] is transformed into the existence of a (quasi) spanning tree of faces in the contraction [Formula: see text]. In particular, we study the case where [Formula: see text] is the leapfrog extension (called vertex envelope of a plane cubic graph [Formula: see text]. 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.