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

Authors M. Abreu, John Baptist Gauci, Jean Paul Zerafa

Publication date 4 April 2021

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

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} i m e s 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 [Electron. J. Combin. 28(1) (2021), #P1.7] 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} i m e s 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

.

This page was built for publication: Saved by the rook: a case of matchings and Hamiltonian cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6364512)