On the minimum order of 4-lazy cops-win graphs

• Published in: Taehan Suhakhoe hoebo 2018, 55(6), , pp.1667-1690
• Main Authors: Kai An Sim, Ta Sheng Tan, Kok Bin Wong
• Format: Article
• Language: English
• Subjects: 수학
• ISSN: 1015-8634; 2234-3016
• DOI: 10.4134/BKMS.b170948

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. KCI Citation Count: 1