Content area
Abstract
We study variations of the pursuit and evasion game Cops and Robber [23, 25] in which one or both of the opposing sides play with constraints.
Both the cops and the robber traditionally play with perfect information. We consider the game when the cops play with only partial information. This partial information is provided first via selected edges of a graph and then via selected vertices. When the partial information includes the robber's direction in addition to his position, we are able to bound the amount of information required by a cop to win on a copwin graph. When the partial information includes only the robber's position, we give bounds on the amount of information required by a cop to win on a tree.
We take steps toward the characterization of graphs with copnumber 2. We consider tandem-win graphs in an attempt to generalize the notion of a copwin graph. We present a recognition theorem for tandem-win graphs, and a characterization of triangle-free tandem-win graphs.
We also consider the game when the cops are restricted to moving on assigned subgraphs. We bound the copnumbers of powers of graphs under a variety of products, and show that in many cases, our results are asymptotically exact. Finally we translate several problems into games where the movements of both the cops and the robber are restricted, and the cop side is reduced to a single cop.
