Problem of the Week 1154The 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 Hamiltonconnected, meaning: Is it possible to get from any square to any other via a Hamiltonian path? We suspect B(m, n) is Hamiltonconnected 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.
