Edge-critical cops and robber in planar graphs.

Abstract: The problem is to determine the number of ‘cops’ needed to capture a ‘robber’ in a game in which the cops always know the location of the robber, and the cops and robber move alternately along edges of a reflexive graph. The cops capture the robber if one of them occupies the same vertex as the robber at any time in the game. A cop-win graph is one in which a single cop has a winning strategy. A graph is cop-win edge-critical with respect to edge addition (respectively, deletion) when the original graph is not cop-win, but the addition (deletion) of any edge results in a cop-win graph. In this paper, edge-critical planar graphs are characterized. [Copyright &y& Elsevier]