When Two-Holed Torus Graphs are Hamiltonian

Abstract

Trotter and Erdös found conditions for when a directed $m\times n$ grid graph on a torus is Hamiltonian. We consider the analogous graphs on a two-holed torus, and study their Hamiltonicity. We find an $\mathcal{O}(n^4)$ algorithm to determine the Hamiltonicity of one of these graphs and an $\mathcal{O}(\log (n))$ algorithm to find the number of diagonals, which are sets of vertices that force the directions of edges in any Hamiltonian cycle. We also show that there is a periodicity pattern in the graphs' Hamiltonicities if one of the sides of the grid is fixed; and we completely classify which graphs are Hamiltonian in the cases where $n=m$, $n=2$, the $m\times n$ graph has $1$ diagonal, or the $\frac{m}{2}\times \frac{n}{2}$ graph has $1$ diagonal.

35 pages and 9 figures