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 ddimensional 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 ddimensional 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 48, 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_{3} x P_{5} x P_{5},
Bulletin of the Institute of Combinatorics and its Applications 42 (2004), 8788.

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 multidimensional meshes into a crossed cube,
Information Processing Letters, 108 (2008) 394397.
Back to list of publications.