Bridged graphs are cop-win graphs: An algorithmic proof (Q1354123)

We consider a game of a cop and a robber on the vertices of an undirected graph: First both players choose their initial position on the graph where the cop begins. Then they move alternately (again, the cop begins) according to the following rule: A player can remain at his actual vertex or move to any neighbour of that vertex. The cop wins when he catches the robber, i.e. when both players occupy the same vertex. The underlying graph is called a cop-win graph if the cop has a winning strategy. Such graphs have been completely characterized by Nowakowski, Winkler, and Quilliot: A graph \(G\) is a cop-win graph if and only if there exists a so-called cop-win ordering \(v_1,v_2,\dots,v_n\) of the vertex-set \(V(G)\), i.e. for each index \(i>1\), there exists some neighbour \(v_j\) of \(v_i\) with \(j<i\) such that each neighbour \(v_k\) of \(v_i\) with \(k<i\) and \(k\neq j\) is also adjacent to \(v_j\). Anstee and Farber proved that all bridged graphs are cop-win graphs (a graph \(G\) is called bridged if each cycle \(C\) in \(G\) of length greater than three contains two vertices whose distance in \(G\) is smaller than in \(C\)). In the present paper, the author gives an algorithmic proof of that result by showing that each linear vertex-ordering of a bridged graph \(G\) produced by a breadth-first-search in \(G\) is a cop-win ordering. Hence cop-win orderings of bridged graphs \(G\) can be constructed in at most \(O(|V(G)|+|E(G)|)\) steps.