Hamiltonian cycles in bipartite toroidal graphs with a partite set of degree four vertices

摘要

Let G be a 3-connected bipartite graph with partite sets X ∪ Y which is embeddable in the torus. We shall prove that G has a Hamiltonian cycle if (i) G is balanced, i.e., |X| = |Y|, and (ii) each vertex x∈ X has degree four. In order to prove the result, we establish a result on orientations of quadrangular torus maps possibly with multiple edges. This result implies that every 4-connected toroidal graph with toughness exactly one is Hamiltonian, and partially solves a well-known Nash-Williams' conjecture.