In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can choose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex (one whose closed neighborhood is a subset of another vertex's neighborhood) or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order. They include the chordal graphs, and the graphs that contain a universal vertex.
Definitions
Pursuit–evasion
Cop-win graphs can be defined by a pursuit–evasion game in which two players, a cop and a robber, are positioned at different initial vertices of a given undirected graph. The cop chooses an initial vertex first, and then the robber chooses. Next, they play in turns, again with the cop first. On each player's turn, the player may either move to an adjacent vertex or stay put. The game ends, and the cop wins, if the cop can end a turn on the same vertex as the robber. The robber wins by indefinitely evading the cop. A cop-win graph is a graph with the property that, when the players choose starting positions and then move in this way, the cop can always force a win. If an undirected graph is not a cop-win graph, it is called a robber-win graph.
Dismantling
The closed neighborhood of a vertex in a given graph is the set of vertices consisting of itself and all other vertices adjacent to . The vertex is said to be dominated by another vertex when . That is, and are adjacent, and every other neighbor of is also a neighbor of . call a vertex that is dominated by another vertex an irreducible vertex.
A dismantling order or domination elimination ordering of a given graph is an ordering of the vertices such that, if the vertices are removed one-by-one in this order, each vertex (except the last) is dominated at the time it is removed. A graph is dismantlable if and only if it has a dismantling order.
Equivalence of cop-win and dismantlability
Every finite dismantlable graph is cop-win. This can be proved by mathematical induction, with a one-vertex graph (trivially won by the cop) as a base case. For a larger graph, let be any dominated vertex. By the induction hypothesis, the cop has a winning strategy on the graph formed by removing , and can follow the same strategy on the original graph by pretending that the robber is on the vertex that dominates whenever the robber is actually on . Following this strategy will result either in an actual win of the game, or in a position where the robber is on and the cop is on the dominating vertex, from which the cop can win in one more move. A cop following this inductive strategy on a graph with vertices takes at most moves to win, regardless of starting position. By choosing the cop's starting position carefully, one can use the same idea to prove that, in an -vertex graph, the cop can force a win in at most moves.
Conversely, every cop-win graph has a dominated vertex. For, in a graph with no dominated vertices, if the robber has not already lost, then there is a safe move to a position not adjacent to the cop, and the robber can continue the game indefinitely by playing one of these safe moves at each turn. Additionally, if is a dominated vertex in a cop-win graph, then removing must produce another cop-win graph, for otherwise the robber could play within that subgraph, pretending that the cop is on the vertex that dominates whenever the cop is actually on , and never get caught. It follows by induction from these two principles that every finite cop-win graph is dismantlable.