Cop number

In graph theory, a branch of mathematics, the cop number or copnumber of an undirected graph is the number of cops to win a certain pursuit-evasion game on the graph.

Rules

In this game, one player controls the position of a given number of cops and the other player controls the position of a robber. The cops are trying to catch the robber by moving to the same position, while the robber is trying to remain uncaught. Thus, the players perform the following actions, taking turns with each other:^[1]

On the first turn of the game, the player controlling the cops places each cop on a vertex of the graph (allowing more than one cop to be placed on the same vertex).
Next, the player controlling the robber places the robber on a vertex of the graph.
On each subsequent turn, the player controlling the cops chooses a (possibly empty) subset of the cops, and moves each of these cops to adjacent vertices. The remaining cops (if any) stay put.
On the robber's turn, he may either move to an adjacent vertex or stay put.

The game ends with a win for the cops whenever the robber occupies the same vertex as a cop. If this never happens, the robber wins.

The cop number of a graph $G$ is the minimum number $k$ such that $k$ cops can win the game on $G$ .^[1]

Example

On a tree, the cop number is one. 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.

By gradually moving closer together, two cops can eventually catch a robber on any cycle (here, a baseball diamond)

On a cycle graph of length more than three, the cop number is two. If there is only one cop, the robber can move to a position two steps away from the cop, and always maintain the same distance after each move of the robber. In this way, the robber can evade capture forever. However, if there are two cops, one can stay at one vertex and cause the robber and the other cop to play in the remaining path. If the other cop follows the tree strategy, the robber will eventually lose.

General results

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.

Unsolved problem in mathematics:

What is the largest possible cop number of an

n

-vertex graph?

(more unsolved problems in mathematics)

Henri Meyniel (also known for Meyniel graphs) conjectured in 1985 that every $n$ -vertex graph has cop number $O({\sqrt {n}})$ . The Levi graphs of finite projective planes have girth six and minimum degree $\Omega ({\sqrt {n}})$ , so if true this bound would be the best possible.^[3] It is known that all graphs have sublinear cop number,^[4] but the problems of obtaining a tight bound, and of proving or disproving Meyniel's conjecture, remain unsolved.^[3]

Computing the cop number of a given graph is EXPTIME-complete,^[5] and hard for parameterized complexity.^[6]

Special classes of graphs

The cop-win graphs are the graphs with cop number equal to one.^[1]

Every planar graph has cop number at most three.^[1] More generally, every graph has cop number at most proportional to its genus.^[7] However, the best known lower bound for the cop number in terms of the genus is approximately the square root of the genus, which is far from the upper bound when the genus is large.^[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. More specifically, on graphs of treewidth $w$ , the cop number is at most $\lfloor w/2\rfloor +1$ .^[8]

References

^ ^a ^b ^c ^d Aigner, M.; Fromme, M. (1984), "A game of cops and robbers", Discrete Applied Mathematics, 8 (1): 1–11, doi:10.1016/0166-218X(84)90073-8, MR 0739593
^ ^a ^b Mohar, Bojan (2017), Notes on Cops and Robber game on graphs, arXiv:1710.11281, Bibcode:2017arXiv171011281M
^ ^a ^b Baird, William; Bonato, Anthony (2012), "Meyniel's conjecture on the cop number: a survey", Journal of Combinatorics, 3 (2): 225–238, arXiv:1308.3385, doi:10.4310/JOC.2012.v3.n2.a6, MR 2980752
^ Frankl, Péter (1987), "Cops and robbers in graphs with large girth and Cayley graphs", Discrete Applied Mathematics, 17 (3): 301–305, doi:10.1016/0166-218X(87)90033-3, MR 0890640
^ Kinnersley, William B. (2015), "Cops and robbers is EXPTIME-complete", Journal of Combinatorial Theory, Series B, 111: 201–220, arXiv:1309.5405, doi:10.1016/j.jctb.2014.11.002, MR 3315605
^ Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan (2008), "On tractability of cops and robbers game", Fifth IFIP International Conference on Theoretical Computer Science—TCS 2008, IFIP Int. Fed. Inf. Process., vol. 273, New York: Springer, pp. 171–185, doi:10.1007/978-0-387-09680-3_12, MR 2757374
^ Schroeder, Bernd S. W. (2001), "The copnumber of a graph is bounded by $\lfloor {\tfrac {3}{2}}\operatorname {genus} (G)\rfloor +3$ ", Categorical perspectives (Kent, OH, 1998), Trends Math., Boston: Birkhäuser, pp. 243–263, MR 1827672
^ Clarke, Nancy Elaine Blanche (2002), Constrained cops and robber, Ph.D. thesis, Canada: Dalhousie University, MR 2704200

[af-1] Aigner, M.; Fromme, M. (1984), "A game of cops and robbers", Discrete Applied Mathematics, 8 (1): 1–11, doi:10.1016/0166-218X(84)90073-8, MR 0739593

[m-2] Mohar, Bojan (2017), Notes on Cops and Robber game on graphs, arXiv:1710.11281, Bibcode:2017arXiv171011281M

[bb-3] Baird, William; Bonato, Anthony (2012), "Meyniel's conjecture on the cop number: a survey", Journal of Combinatorics, 3 (2): 225–238, arXiv:1308.3385, doi:10.4310/JOC.2012.v3.n2.a6, MR 2980752

[f-4] Frankl, Péter (1987), "Cops and robbers in graphs with large girth and Cayley graphs", Discrete Applied Mathematics, 17 (3): 301–305, doi:10.1016/0166-218X(87)90033-3, MR 0890640

[k-5] Kinnersley, William B. (2015), "Cops and robbers is EXPTIME-complete", Journal of Combinatorial Theory, Series B, 111: 201–220, arXiv:1309.5405, doi:10.1016/j.jctb.2014.11.002, MR 3315605

[fgk-6] Fomin, Fedor V.; Golovach, Petr A.; Kratochvíl, Jan (2008), "On tractability of cops and robbers game", Fifth IFIP International Conference on Theoretical Computer Science—TCS 2008, IFIP Int. Fed. Inf. Process., vol. 273, New York: Springer, pp. 171–185, doi:10.1007/978-0-387-09680-3_12, MR 2757374

[s-7] Schroeder, Bernd S. W. (2001), "The copnumber of a graph is bounded by $\lfloor {\tfrac {3}{2}}\operatorname {genus} (G)\rfloor +3$ ", Categorical perspectives (Kent, OH, 1998), Trends Math., Boston: Birkhäuser, pp. 243–263, MR 1827672

[c-8] Clarke, Nancy Elaine Blanche (2002), Constrained cops and robber, Ph.D. thesis, Canada: Dalhousie University, MR 2704200

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]