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

2018/06/14 by Gh., Behrooz Bagheri, Feder, Tomas, Fleischner, Herbert +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1806.05483

Abstract

We study the existence of hamiltonian cycles in plane cubic graphs G having a facial 2-factor Q. Thus hamiltonicity in G is transformed into the existence of a (quasi) spanning tree of faces in the contraction G/Q. In particular, we study the case where G is the leapfrog extension (called vertex envelope in (Discrete Math., 309(14):4793-4809, 2009)) of a plane cubic graph G₀. 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 (Israel J. Math., 22:52-56, 1975).

Cited by

• Putting Tutte's counterexample to Tait's conjecture in perspective to Hamiltonicity and non-Hamiltonicity in certain planar cubic graphs

Related

• Algorithmic proof of Barnette's Conjecture
• Barnette Graphs with Faces up to Size 8 are Hamiltonian
• Hamiltonian cycles in some family of cubic 3-connected plane graphs
• A sufficient condition for cubic 3-connected plane bipartite graphs to be hamiltonian
• On the algorithmic complexity of finding hamiltonian cycles in special classes of planar cubic graphs