On the minimum order of k-cop win graphs

2012/07/10 by William Baird, Andrew Beveridge, Anthony Bonato +4 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Combinatorics #Mathematics #Discrete mathematics #Graph #Line graph #Cubic graph #Voltage graph

paper · doi:10.11575/cdm.v9i1.62207

openalex publication_date 2012/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

• Vertex-to-vertex pursuit in a graph

Cited by

• Petersen graph [wikipedia]

Related

• On the minimum order of k-cop-win graphs
• The Petersen graph is the smallest 3-cop-win graph
• 4-cop-win graphs have at least 19 vertices
• Meyniel’s conjecture on the cop number: A survey
• Most Generalized Petersen graphs of girth 8 have cop number 4