On the minimum order of k-cop-win graphs

2013/08/13 by William Baird, Andrew Beveridge, Baird, William +11
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1308.2841

arXiv admin note: substantial text overlap with arXiv:1110.0768

arxiv created 2013/08/13 · arxiv updated 2013/08/14

Abstract

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.

Citations

• The Petersen graph is the smallest 3-cop-win graph

Related

• The Petersen graph is the smallest 3-cop-win graph
• 4-cop-win graphs have at least 19 vertices
• On Generalised Petersen Graphs of Girth 7 that have Cop Number 4
• Most Generalized Petersen graphs of girth 8 have cop number 4
• Meyniel's conjecture on the cop number: a survey