Bent Hamilton Cycles

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.

Appears in Electronic Journal of Combinatorics, #R1, 10 (2003) 18 pages.
Presented at the 33rd Southeastern International Conference on Combinatorics Graph Theory and Computing (link), March 4-8, 2002.
The conjecture that Q(3,5,5) does not have a Hamilton path has been proven correct by Patric R. J. Östergård (patric.ostergard(AT)hut.fi), On the nonexistence of bent Hamiltonian paths in the grid graph P₃ x P₅ x P₅, Bulletin of the Institute of Combinatorics and its Applications 42 (2004), 87-88.
Joe Sawada is now a faculty member at the University of Guelph.

Selected citations to this paper:

Qiang Donga, Xiaofan Yanga and Juan Zhaob, Embedding a family of disjoint multi-dimensional meshes into a crossed cube, Information Processing Letters, 108 (2008) 394-397.

Back to list of publications.