Bridged graphs are cop-win graphs: An algorithmic proof

A graph is bridged if 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 ordering upsilon(1), upsilon(2), ..., upsilon(n) such that every vertex upsilon(i), i > 1, is dominated by some neighbour upsilon(j), j < i, i.e., every vertex upsilon(k), k < i, adjacent to upsilon(i) is adjacent to upsilon(j), too. We present an alternative proof of the result of Anstee and Farber, which allows us to find such an ordering in rime 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.'' (C) 1997 Academic Press.