On the minimum order of 4-lazy cops-win graphs
Document Type
Article
Publication Date
1-1-2018
Abstract
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 □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 ∆(G) ≥ n − k 2 , c L (G) ≤ 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 ∆(G) ≤ 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
Divisions
MathematicalSciences
Funders
Postgraduate Research Grant (PPP)-Research PG068-2015A by University of Malaya
Publication Title
Bulletin of the Korean Mathematical Society
Volume
55
Issue
6
Publisher
Korean Mathematical Society