Bent Hamilton Cycles in Grid Graphs

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Joe Sawada, Department of Computer Science, University of Victoria, Canada.

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 > 3, and does not have a bent Hamilton path if all dimensions are odd. For the d-dimensional wrapped 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 > 3. In the latter case, we determine the conditions for when a bent Hamilton path exists. We also show that if d = 2, then there exists a bent Hamilton cycle if and only if both dimensions are even.



Selected citations to this paper:
Back to list of publications.