Saved by the rook : a case of matchings and Hamiltonian cycles

Abstract

The rook graph is a graph whose edges represent all the possible legal moves of the rook chess piece on a chessboard. The problem we consider is the following. Given any set M containing pairs of cells such that each cell of the m1×m2 chessboard is in exactly one pair, we determine the values of the positive integers m1 and m2 for which it is possible to construct a closed tour of all the cells of the chessboard which uses all the pairs of cells in M and some edges of the rook graph. This is an alternative formulation of a graph-theoretical problem presented in [1] involving the Cartesian product G of two complete graphs Km1 and Km2 , which is, in fact, isomorphic to the m1×m2 rook graph. The problem revolves around determining the values of the parameters m1 and m2 that would allow any perfect matching of the complete graph on the same vertex set of G to be extended to a Hamiltonian cycle by using only edges in G.