A Complete Solution of 3-Hamiltonian Grids and Torus Graphs

Gee-Choon Lau, Sin-Min Lee, Karl Schaffer, Siu-Ming Tong

Abstract

For a $(p, q)$-graph $G$, if the vertices of $G$ can be arranged in a sequence $v_1, v_2, \ldots, v_p$ such that for each $i = 1, 2, \ldots, p-1$, the distance from $v_i$ to $v_{i+1}$ equal to $k$, then the sequence is called an $AL(k)$-step traversal. Furthermore, if $d(v_p,v_1) = k$, the sequence $v_1, v_2, \ldots, v_p, v_1$ is called a $k$-step Hamiltonian tour and $G$ is $k$-step Hamiltonian. In this paper we completely determine which rectangular grid graphs are 3-step Hamiltonian and show that the torus graph $C_m \times C_n$ is 3-step Hamiltonian for all $m \ge 3, n \ge 5$.