On the minimum order of k-cop-win graphs
| Autor: | Baird, William, Beveridge, Andrew, Bonato, Anthony, Codenotti, Paolo, Maurer, Aaron, McCauley, John, Valeva, Silviya |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We consider the minimum order graphs with a given cop number. We prove that the minimum order of a connected graph with cop number 3 is 10, and show that the Petersen graph is the unique isomorphism type of graph with this property. We provide the results of a computational search on the cop number of all graphs up to and including order 10. A relationship is presented between the minimum order of graph with cop number $k$ and Meyniel's conjecture on the asymptotic maximum value of the cop number of a connected graph. Comment: arXiv admin note: substantial text overlap with arXiv:1110.0768 |
| Databáze: | arXiv |
| Externí odkaz: |
|