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 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. 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. 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] ⊂ N[w]. That is, v and w are adjacent, and every other neighbor of v is also a neighbor of w. 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.