Cops against a cheating robber

We investigate a cheating robot version of Cops and Robber, first introduced by Huggan and Nowakowski, where both the cops and the robber move simultaneously, but the robber is allowed to react to the cops’ moves. For conciseness, we refer to this game as Cops and Cheating Robot. The cheating robot number for a graph is the fewest cops needed to win on the graph. We introduce a new parameter for this variation, called the push number, which is the minimum number of cops that move onto the robber’s vertex in a game of Cops and Cheating Robot given that there are a cheating robot number of cops on the graph. After producing some elementary results on the push number, we use it to give a relationship between Cops and Cheating Robot and Surrounding Cops and Robbers. We investigate the cheating robot number for planar graphs and give a tight bound for bipartite planar graphs. We show that for a fixed k ∈ Z + , determining whether a graph has a cheating robot number at most k can be done in polynomial time. We also obtain bounds on the cheating robot number for strong and lexicographic products of graphs.