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 □K 3 is the unique graph on nine vertices which requires three lazy cops. They conjectured that...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Korean Mathematical Society
2018
|
| Subjects: |
| 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 □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. |
|---|