On the Minimal Order of $k$-Cop-Win Graphs
Published in Contributions to Discrete Mathematics, 2014
W. Baird, A. Beveridge, A. Bonato, P. Codenotti, J. MacCauley, A. Maurer, S. Valeva, On the Minimal Order of $k$-Cop-Win Graphs, Contributions to Discrete Mathematics, Vol 9, No. 1 (2014), pp. 1-15.
Preprint link: https://arxiv.org/abs/1308.2841
The cop number of a graph is the minimum number of cops needs to capture a robber moving between vertices of the graph. 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.