A sufficient condition for cubic 3-connected plane bipartite graphs to be hamiltonian

Abstract

Barnette's conjecture asserts that every cubic $3$-connected plane bipartite graph is hamiltonian. Although, in general, the problem is still open, some partial results are known. In particular, let us call a face of a plane graph big (small) if it has at least six edges (it has four edges, respectively). Goodey proved for a $3$-connected bipartite cubic plane graph $P$, that if all big faces in $P$ have exactly six edges, then $P$ is hamiltonian. In this paper we prove that the same is true under the condition that no face in $P$ has more than four big neighbours. We also prove, that if each vertex in $P$ is incident both with a small and a big face, then~$P$ has at least $2^k$ different Hamilton cycles, where $k=\lceil \frac{|B|-2}{4\hat{I}”(B)-7}\rceil$, $|B|$ is the number of big faces in $P$ and $\hat{I}”(B)$ is the maximum size of faces in $P$. 15 pages

15 pages