On the minimum order of 4-lazy cops-win graphs
Bull. Korean Math. Soc. 2018 Vol. 55, No. 6, 1667-1690
Published online November 1, 2018
Kai An Sim, Ta Sheng Tan, Kok Bin Wong
University of Reading Malaysia, University of Malaya, University of Malaya
Abstract : 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
Full-Text :


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd