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 $m_1 \times m_2$ chessboard is in exactly one pair, we determine the values of the positive integers $m_1$ and $m_2$ 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 Marién Abreu, John Baptist Gauci, Domenico Labbate, Giuseppe Mazzuoccolo, and Jean Paul Zerafa, Extending perfect matchings to Hamiltonian cycles in line graphs, Electron. J. Comb. 28 (2021), no.~1, research paper p1.7, 13 (English) involving the Cartesian product $G$ of two complete graphs $K_{m_1}$ and $K_{m_2}$, which is, in fact, isomorphic to the $m_{1}\times m_{2}$ rook graph. The problem revolves around determining the values of the parameters $m_1$ and $m_2$ 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$.