2023/09/18 by Florek, Jan · 1 citation
#05C05 #05C10 #05C45 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.09578
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 2k different Hamilton cycles, where k = \lceil(|B|-2)/(4Δ(B) - 7)\rceil, |B| is the number of big faces in P and Δ(B) is the maximum size of faces in P. 15 pages