Journal of Combinatorics
Volume 14 (2023)
Pursuit-evasion games on Latin square graphs
Pages: 461 – 483
We investigate various pursuit-evasion parameters on Latin square graphs, including the cop number, metric dimension, and localization number. Bounds for the cop number are given for Latin square graphs and for similarly defined graphs corresponding to $k$ mutually orthogonal Latin squares of order $n$. If $n \gt (k+1)^2$, then the cop number is shown to be $k+2$. Lower and upper bounds are provided for the metric dimension and localization number of Latin square graphs. An analysis of the metric dimension of back-circulant Latin squares shows that the lower bound is close to tight.
Latin squares, graphs, mutually orthogonal Latin squares, cop number, metric dimension, localization number
2010 Mathematics Subject Classification
Primary 05C57. Secondary 05B15.
The second author acknowledges funding from an NSERC Discovery Grant. The first, third, fourth, and six authors conducted research for the paper within the 2021 Fields Undergraduate Summer Research Program. The fifth author was supported by funds from NSERC and The Fields Institute for Research in Mathematical Sciences.
Received 30 September 2021
Accepted 5 September 2022
Published 14 April 2023