Cop number
In graph theory, a branch of mathematics, the cop number or copnumber of an undirected graph is the minimum number of cops that suffices to ensure a win (i.e., a capture of the robber) in a certain pursuit–evasion game on the graph.
Thus, the players perform the following actions, taking turns with each other:[1] The game ends with a win for the cops whenever the robber occupies the same vertex as a cop.
The cop can start anywhere, and at each step move to the unique neighbor that is closer to the robber.
Each of the cop's steps reduces the size of the subtree that the robber is confined to, so the game eventually ends.
On a cycle graph of length more than three, the cop number is two.
If the other cop follows the tree strategy, the robber will eventually lose.
Every graph whose girth is greater than four has cop number at least equal to its minimum degree.
[2] It follows that there exist graphs of arbitrarily high cop number.
Two types of subgraph that are guardable are the closed neighborhood of a single vertex, and a shortest path between any two vertices.
The Moore bound in the degree diameter problem implies that at least one of these two kinds of guardable sets has size
[3][4] A more strongly sublinear upper bound on the cop number, is known.
However, the problems of obtaining a tight bound, and of proving or disproving Meyniel's conjecture, remain unsolved.
It is even unknown whether the soft Meyniel conjecture, that there exists a constant
[3] Computing the cop number of a given graph is EXPTIME-hard,[5] and hard for parameterized complexity.
[1] More generally, every graph has cop number at most proportional to its genus.
[2] The treewidth of a graph can also be obtained as the result of a pursuit-evasion game, but one in which the robber can move along arbitrary-length paths instead of a single edge in each turn.
This extra freedom means that the cop number is generally smaller than the treewidth.
