Cop-win graph

In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit-evasion game in which he chases a robber, the players alternately moving along an edge of a graph or staying 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.

Cop-win graphs (and the complementary class of graphs, robber-win graphs) were introduced by Nowakowski & Winkler (1983) in the context of the following pursuit-evasion game, whose invention they credit to G. Gabor and A. Quilliot. Two players, a cop and a robber, are positioned at different initial vertices of a given graph. They play in turns; 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 his 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, no matter where the two players start, the cop can always force a win.

The closed neighborhood $N [v]$ of a vertex $v$ in a given graph is the set of vertices consisting of $v$ itself and all other vertices adjacent to $v$ . The vertex $v$ is said to be dominated by another vertex $w$ when $N [v] \subset N [w]$ . That is, $v$ and $w$ are adjacent, and every other neighbor of $v$ is also a neighbor of $w$ .Nowakowski & Winkler (1983) call a vertex that is dominated by another vertex an irreducible vertex.

...
Wikipedia