Bull. Korean Math. Soc. 2018; 55(6): 1667-1690
Online first article November 9, 2018 Printed November 1, 2018
https://doi.org/10.4134/BKMS.b170948
Copyright © The Korean Mathematical Society.
Kai An Sim, Ta Sheng Tan, Kok Bin Wong
University of Reading Malaysia, University of Malaya, University of Malaya
We consider the minimum order of a graph $G$ with a given lazy cop number $c_L(G)$. Sullivan, Townsend and Werzanski \cite{k=3} showed that the minimum order of a connected graph with lazy cop number 3 is 9 and $K_3$ \Box $K_3$ is the unique graph on nine vertices which requires three lazy cops. They conjectured that for a graph $G$ on $n$ vertices with $\Delta (G) \geq n-k^2$, $c_L(G) \leq k$. We proved that the conjecture is true for $k=4$. Furthermore, we showed that the Petersen graph is the unique connected graph $G$ on 10 vertices with $\Delta(G) \leq 3$ having lazy cop number 3 and the minimum order of a connected graph with lazy cop number 4 is 16.
Keywords: Cops and Robbers, vertex-pursuit games, minimum order
MSC numbers: 05C57, 05C80
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd