Simultaneous Moves with Cops and an Insightful Robber
share
The 'Cheating Robot' is a simultaneous play, yet deterministic, version of Cops and Robbers played on a finite, simple, connected graph. The robot knows where the cops will move on the next round and has the time to react. The cops also know that the robot has inside information. More cops are required to capture a robot than to capture a robber. Indeed, the minimum degree is a lower bound on the number of cops required to capture a robot. Only on a tree is one cop guaranteed to capture a robot, although two cops are sufficient to capture both a robber and a robot on outerplanar graphs. In graphs where retracts are involved, we show how cop strategies against a robber can be modified to capture a robot. This approach gives exact numbers for hypercubes, and k-dimensional grids in general.
READ FULL TEXT