\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf F. Ruskey and Joe Sawada }
%
%
\medskip
\noindent
%
%
{\bf Bent Hamilton Cycles in $d$-Dimensional Grid Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
A {\it 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.


\bye

.
