TOPICS
Search

Cop Number


The cop number c(G) of a finite graph G is the least number of cops that can guarantee capture of a robber in the following combinatorial game (Nowakowski and Winkler 1983). The cops choose starting vertices, then the robber chooses a starting graph vertex. The players alternate turns, with the cops moving first. On a turn, each cop, or the robber, may remain in place or move to an adjacent vertex. Both sides know all positions, and capture occurs when a cop and the robber occupy the same graph vertex. In the lazy variant, at most one cop moves on each cop turn. Its minimum team size is the lazy cop number c_L(G), which satisfies c(G)<=c_L(G).

Ghai (2026) proved c_L(G)<=3 whenever a connected graph has a cyclic arrangement of parts such that each part is dominated by a single graph vertex and every graph edge joins the same part or consecutive parts. The strategy uses two stationary cops to confine the robber while a third moves the boundary inward. The result applies to flower snarks. Ghai (2026) reports Claude assistance with proof strategies, computational checks, and Lean formalization.


See also

Combinatorial Game, Graph

Explore with Wolfram|Alpha

References

Nowakowski, R. and Winkler, P. "Vertex-to-Vertex Pursuit in a Graph." Disc. Math. 43, 235-239, 1983. https://doi.org/10.1016/0012-365X(83)90160-7.Ghai, A. "The Cop Number of the Flower Snarks, and the Generalized Petersen Graphs with Cop Number Two." 12 Nov 2026. https://arxiv.org/abs/2611.18787v1.

Cite this as:

Weisstein, Eric W. "Cop Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CopNumber.html

Subject classifications