Hamiltonian cycles in annular decomposable Barnette graphs
Saptarshi Bej · Journal of Discrete Mathematical Sciences and Cryptography · 2022
Barnette’s conjecture is an unsolved problem in graph theory. The problem states that every 3-regular (cubic), 3-connected, planar, bipartite (Barnette) graph is Hamiltonian. Partial results have been derived with restrictions on the number of vertices, several properties of face-partitions and dual graphs of Barnette graphs, while some studies focus just on structural characterizations of Barnette graphs. Noting that spider web graphs are a subclass of Annular Decomposable Barnette (ADB graphs) graphs and are Hamiltonian, we study ADB graphs and their annular-connected subclass (ADB-AC graphs). We show that ADB-AC graphs can be generated from the smallest Barnette graph (B0) using recursive edge operations. We derive several conditions assuring the existence of Hamiltonian cycles in ADB-AC graphs without imposing restrictions on the number of vertices, face size or any other constraints on the face partitions. We show that there can be two types of annuli in ADB-AC graphs, ring annuli and block annuli. Our main result is, ADB-AC graphs having non-singular sequences of ring annuli are Hamiltonian.