- Current Issue - Ahead of Print Articles - All Issues - Search - Open Access - Information for Authors - Downloads - Guideline - Regulations ㆍPaper Submission ㆍPaper Reviewing ㆍPublication and Distribution - Code of Ethics - For Authors ㆍOnlilne Submission ㆍMy Manuscript - For Reviewers - For Editors
 On the minimum order of 4-lazy cops-win graphs Bull. Korean Math. Soc. 2018 Vol. 55, No. 6, 1667-1690 https://doi.org/10.4134/BKMS.b170948Published 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 Downloads: Full-text PDF