Journal of Combinatorics

Volume 14 (2023)

Number 4

Pursuit-evasion games on Latin square graphs

Pages: 461 – 483

DOI: https://dx.doi.org/10.4310/JOC.2023.v14.n4.a4

Authors

Shreya Ahirwar (Department of Mathematics & Statistics, Mount Holyoke College, South Hadley, Massachusetts, U.S.A.)

Anthony Bonato (Department of Mathematics, Toronto Metropolitan University, Toronto, Ontario, Canada)

Leanna Gittins (Department of Mathematics & Statistics, McMaster University, Hamilton, Ontario, Canada)

Alice Huang (Department of Mathematics, University of Toronto, Ontario, Canada)

Trent G. Marbach (Department of Mathematics, Toronto Metropolitan University, Toronto, Ontario, Canada)

Tomer Zaidman (Department of Mathematics, University of Toronto, Ontario, Canada)

Abstract

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.

Keywords

Latin squares, graphs, mutually orthogonal Latin squares, cop number, metric dimension, localization number

2010 Mathematics Subject Classification

Primary 05C57. Secondary 05B15.

Full Text (PDF format)

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