ON THE MINIMUM ORDER OF 4-LAZY COPS-WIN GRAPHS

We consider the minimum order of a graph G with a given lazy cop number $c_L(G)$. Sullivan, Townsend and Werzanski [7] showed that the minimum order of a connected graph with lazy cop number 3 is 9 and $k_3{\square}k_3$ is the unique graph on nine vertices which requires three lazy cops. They conjec...

Full description

Saved in:
Bibliographic Details
Published in:Taehan Suhakhoe hoebo 2018, Vol.55 (6), p.1667-1690
Main Authors: Sim, Kai An, Tan, Ta Sheng, Wong, Kok Bin
Format: Article
Language:Korean
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the minimum order of a graph G with a given lazy cop number $c_L(G)$. Sullivan, Townsend and Werzanski [7] showed that the minimum order of a connected graph with lazy cop number 3 is 9 and $k_3{\square}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.
ISSN:1015-8634