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: |
| _version_ | 1825721541357207552 |
|---|---|
| author | Sim, Kai An Tan, Ta Sheng Wong, Kok Bin |
| author_facet | Sim, Kai An Tan, Ta Sheng Wong, Kok Bin |
| author_sort | Sim, Kai An |
| collection | UM |
| description | 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. |
| first_indexed | 2024-03-06T05:51:51Z |
| format | Article |
| id | um.eprints-20660 |
| institution | Universiti Malaya |
| last_indexed | 2024-03-06T05:51:51Z |
| publishDate | 2018 |
| publisher | Korean Mathematical Society |
| record_format | dspace |
| spelling | um.eprints-206602019-03-12T02:03:05Z http://eprints.um.edu.my/20660/ On the minimum order of 4-lazy cops-win graphs Sim, Kai An Tan, Ta Sheng Wong, Kok Bin Q Science (General) QA Mathematics 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. Korean Mathematical Society 2018 Article PeerReviewed Sim, Kai An and Tan, Ta Sheng and Wong, Kok Bin (2018) On the minimum order of 4-lazy cops-win graphs. Bulletin of the Korean Mathematical Society, 55 (6). pp. 1667-1690. ISSN 1015-8634, DOI https://doi.org/10.4134/BKMS.b170948 <https://doi.org/10.4134/BKMS.b170948>. http://pdf.medrang.co.kr/kms01/BKMS/55/BKMS-55-6-1667-1690.pdf doi:10.4134/BKMS.b170948 |
| spellingShingle | Q Science (General) QA Mathematics Sim, Kai An Tan, Ta Sheng Wong, Kok Bin On the minimum order of 4-lazy cops-win graphs |
| title | On the minimum order of 4-lazy cops-win graphs |
| title_full | On the minimum order of 4-lazy cops-win graphs |
| title_fullStr | On the minimum order of 4-lazy cops-win graphs |
| title_full_unstemmed | On the minimum order of 4-lazy cops-win graphs |
| title_short | On the minimum order of 4-lazy cops-win graphs |
| title_sort | on the minimum order of 4 lazy cops win graphs |
| topic | Q Science (General) QA Mathematics |
| work_keys_str_mv | AT simkaian ontheminimumorderof4lazycopswingraphs AT tantasheng ontheminimumorderof4lazycopswingraphs AT wongkokbin ontheminimumorderof4lazycopswingraphs |