Bent Hamilton cycles in \(d\)-dimensional grid graphs
type: Item
instance of: scholarly article
title: Bent Hamilton cycles in \(d\)-dimensional grid graphs
zbMATH Open document ID: 1012.05105
author: Frank Ruskey
author: Joe Sawada
published in: The Electronic Journal of Combinatorics
publication date: 2003-05-13T00:00:00Z
full work available at URL: https://eudml.org/doc/122635
full work available at URL: v10i1r1.html
review text: A bent Hamilton cycle in a grid graph is one on which each edge in a successive pair of edges lies in a different dimension. In the paper it is shown that the \(d\)-dimensional grid graph has a bent Hamilton cycle if some dimension is even and \(d\geq 3\), and it does not have a bent Hamilton cycle if all dimensions are odd. In the latter case, conditions are determined for a bent Hamilton path to exist. For the \(d\)-dimensional toroidal grid graph (i.e., the graph product of \(d\) cycles), the authors show that there exists a bent Hamilton cycle when all dimensions are odd and \(d\geq 3\). It is also shown that if \(d=2\), then there exists a bent Hamilton cycle if and only if both dimensions are even.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1862494
zbMATH Keywords: bent Hamilton
zbMATH Keywords: grid graph
zbMATH Keywords: \(d\)-dimensional
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1862494