The game of Overprescribed Cops and Robbers played on graphs

2016/11/23 by Anthony Bonato, Xavier Pérez‐Giménez, Bonato, Anthony +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1611.07592

openalex publication_date 2016/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the effect on the length of the game of Cops and Robbers when more cops are added to the game play. In Overprescribed Cops and Robbers, as more cops are added, the capture time (the minimum length of the game assuming optimal play) monotonically decreases. We give the full range of capture times for any number of cops on trees, and classify the capture time for an asymptotic number of cops on grids, hypercubes, and binomial random graphs. The capture time of planar graphs with a number of cops at and far above the cop number is considered.

Citations

• On the Cop Number of a Graph
• Vertex-to-vertex pursuit in a graph

Related

• The capture time in the game of cops and many robbers
• Bounds on the length of a game of Cops and Robbers
• Capture-time Extremal Cop-Win Graphs
• Capture times in the Bridge-burning Cops and Robbers game
• The capture time of the hypercube