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.

Denis Peskov, Nancy Clarke, Jason Krone, Brigi Fodor, Yi Zhang, Adel Youssef, Mona Diab. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.