Lazy Cops and Robber on Certain Cayley Graph
DOI:
https://doi.org/10.11113/mjfas.v18n2.2235Abstract
The lazy cop number is the minimum number of cops needed for the cops to have a winning strategy in the game of Cops and Robber where at most one cop may move in any one round. This variant of the game of Cops and Robber, called Lazy Cops and Robber, was introduced by Offner and Ojakian, who provided bounds for the lazy cop number of hypercubes. In this paper, we are interested in the game of Lazy Cops and Robber on a Cayley graph of n copies of Zm+1.
References
M. Aigner and M. Fromme, A game of cops and robbers, Discrete Appl. Math. 8, 1–12, 1984.
N. Alon and J. Spencer, The Probabilistic Method, 6th ed. New Jersey: John Wiley & Sons, 2016.
D. Bal, A. Bonato, W. Kinnersley and P. Pralat, Lazy Cops and Robbers on hypercubes, Combin. Probab. Comput., 24(6), 829–837, 2015.
D. Bal, A. Bonato, W. Kinnersley and P. Pralat, Lazy Cops and Robbers Played on Random Graphs and Graphs on Surfaces,Int. J. Comb. 7(4), 627–642, 2016.
A. Bonato and R. J. Nowakowski, The Games of Cops and Robbers on Graphs, Providence, Rhode Island: American Mathematical Society, 2011.
P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.
P. Frankl, Cops and robbers in graphs with large girth and Cayley graphs, Discrete Appl. Math. 17, 301–305, 1987.
R. J. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43, 235–239, 1983.
D. Offner and K. Ojakian, Variations of cops and robber on the hypercube, Australas.J. Combin. 59(2), 229–250, 2014.
A. Quilliot, Jeux et pointes fixes sur les graphes. Thèse de 3ème cycle, Université de Paris VI, 31–145, 1978.
K. A. Sim, T. S. Tan, K. B. Wong, Lazy cops and robbers on generalized hypercubes, Discrete Math. 340, 1693–1704, 2017.
K. A. Sim, T. S. Tan, K. B. Wong, On the minimum order of 4-lazy cops-win graphs, Bull. Korean Math. Soc. 55, 1667–1690, 2018.
B. W. Sullivan, N. Townsend and M. Werzanski, An Introduction to Lazy Cops and Robbers on Graphs, College Math. J. 48, 322–333, 2017.
B. W. Sullivan, N. Townsend and M. Werzanski, The 3 × 3 rooks graph ( K3□K3 ) is the unique smallest graph with lazy cop number 3, arXiv: 1606.08485v, 12018
Downloads
Published
Issue
Section
License
Copyright (c) 2022 Kai An Sim, Ta Sheng Tan, Kok Bin Wong
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
