Bridged Graphs Are Cop-Win Graphs: An Algorithmic Proof

A graph isbridgedif it contains no isometric cycles of length greater than three. Anstee and Farber established that bridged graphs are cop-win graphs. According to Nowakowski and Winkler and Quilliot, a graph is a cop-win graph if and only if its vertices admit a linear orderingv1, v2, …, vnsuch that every vertexvi,i>1, is dominated by some neighbourvj,j<i, i.e., every vertexvk,k<i, adjacent toviis adjacent tovj, too. We present an alternative proof of the result of Anstee and Farber, which allows us to find such an ordering in time linear in the number of edges. Namely, we show that every ordering of the vertices of a bridged graph produced by the breadth-first search is a “cop-win ordering.”