Bent Hamilton Cycles in $d$-Dimensional Grid Graphs

  • F. Ruskey
  • Joe Sawada

Abstract

A bent Hamilton cycle in a grid graph is one in which each edge in a successive pair of edges lies in a different dimension. We show that the $d$-dimensional grid graph has a bent Hamilton cycle if some dimension is even and $d \geq 3$, and does not have a bent Hamilton cycle if all dimensions are odd. In the latter case, we determine the conditions for when a bent Hamilton path exists. For the $d$-dimensional toroidal grid graph (i.e., the graph product of $d$ cycles), we show that there exists a bent Hamilton cycle when all dimensions are odd and $d \geq 3$. We also show that if $d=2$, then there exists a bent Hamilton cycle if and only if both dimensions are even.

Published
2003-01-06
Article Number
R1