Bent Hamilton cycles in \(d\)-dimensional grid graphs
The electronic journal of combinatorics, Tome 10 (2003)
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.
DOI :
10.37236/1694
Classification :
05C45, 05C38
Mots-clés : bent Hamilton, grid graph, \(d\)-dimensional
Mots-clés : bent Hamilton, grid graph, \(d\)-dimensional
@article{10_37236_1694,
author = {F. Ruskey and Joe Sawada},
title = {Bent {Hamilton} cycles in \(d\)-dimensional grid graphs},
journal = {The electronic journal of combinatorics},
year = {2003},
volume = {10},
doi = {10.37236/1694},
zbl = {1012.05105},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1694/}
}
F. Ruskey; Joe Sawada. Bent Hamilton cycles in \(d\)-dimensional grid graphs. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1694
Cité par Sources :