Hamilton Cycles in Cubic Polyhex Graphs on the Klein Bottle

Abstract

Let \(G\) be a connected cubic graph embedded on a surface \(\Sigma\) such that every face is bounded by a cycle of length \(6\). By Euler formula, \(\Sigma\) is either the torus or the Klein bottle. The corresponding graphs are called toroidal polyhex graphs and Klein-bottle polyhex graphs, respectively. It was proved that every toroidal polyhex graph is hamiltonian. In this paper, we prove that every Klein-bottle polyhex graph is hamiltonian. Furthermore, lower bounds for the number of Hamilton cycles in Klein-bottle polyhex graphs are obtained.