Trotter and Erdos 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.
تحميل البحث