Problem of the Week 1154
The Wandering Bishop
Suppose a bishop is on the lower left square (assumed to be white) of an
Harder, but doable: For which pairs of positive integers (m, n) does the (white) bishop graph B(m, n) on an m x n board have a Hamiltonian cycle?
Notes: A bishop moves along diagonals of a chessboard. A white bishop can only move to white squares. The problem is asking for a Hamiltonian cycle in the (white) bishop's graph B(m, n) for an m x n board. Peter Saltzman and I have characterized the cases where B(m, n) is Hamiltonian.
Open question: Are the bishop's graphs Hamilton-connected, meaning: Is it possible to get from any square to any other via a Hamiltonian path? We suspect B(m, n) is Hamilton-connected except in some easily handled negative cases: m <= 3 and B(4, 4).
Source: Joint work in summer 2012 by Peter Saltzman and Stan Wagon. It appears that the problem had been considered before but not in the pure graph sense; that is, a move from A to B over C was considered as having visited C. We are interested here in the purer problem about certain graphs being Hamiltonian.
© Copyright 2012 Stan Wagon. Reproduced with permission.
23 September 2012