Copnumber of Graphs With Strong Isometric Dimension Two

Shannon L. Fitzpatrick1, Richard J. Nowakowski2
1Acadia University Wolfville, Nova Scotia
2Dathouste University Halifax, Nova Scotia

Abstract

The problem is to determine the number of `cops’ needed to capture a `robber’ where the game is played with perfect information with the cops and the robber alternating moves. The `cops’ capture the `robber’ if one of them occupies the same vertex as the robber at any time in the game. Here we show that a graph with strong isometric dimension two requires no more than two cops.