We introduce the bodyguard problem for graphs. This is a variation of Surrounding Cops and Robber but, in this model, a smallest possible group of bodyguards must surround the president and then maintain this protection indefinitely. We investigate some general bounds, then solve this problem for complete graphs, wheels, trees, cycles, complete multipartite graphs, and two-dimensional grids. We also examine the problem in more general Cartesian, strong, and lexicographic products.

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.

The deduction game is a variation of the game of cops and robber on graphs in which searchers must capture an invisible evader in at most one move. Searchers know each others’ initial locations, but can only communicate if they are on the same vertex. Thus, searchers must deduce other searchers’ movement and move accordingly. We introduce the deduction number and study it for various classes of graphs. We provide upper bounds for the deduction number of the Cartesian product of graphs.

We introduce the game of Cat Herding, where an omnipresent herder slowly cuts down a graph until an evasive cat player has nowhere to go. The number of cuts made is the score of a game, and we study the score under optimal play. In this paper, we begin by deriving some general results, and then we determine the precise cat number for paths, cycles, stars, and wheels. Finally, we identify an optimal Cat and Herder strategy on complete graphs, while providing both a recurrence and closed form for cat ( K n ) .