Search

We introduce the game of Surrounding Cops and Robbers on a graph, as a variant of the original game of Cops and Robbers. In contrast to the original game in which the cops win by occupying the same vertex as the robber, they now win by occupying each of the robber’s neighbouring vertices. We denote by σ ( G ) the surrounding cop number of G , namely the least number of cops required to surround a robber in the graph G . We present a number of results regarding this parameter, including general bounds as well as exact values for several classes of graphs. Particular classes of interest include product graphs, graphs arising from combinatorial designs, and generalised Petersen graphs.

We consider a variation of the Cops and Robber game where the cops can only see the robber when the distance between them is at most a fixed parameter l . We consider the basic consequences of this definition for some simple graph families, and show that this model is not monotonic, unlike common models where the robber is invisible. We see that cops’ strategy consists of a phase in which they need to “see” the robber (move within distance l of the robber), followed by a phase in which they capture the robber. In some graphs the first phase is the most resource intensive phase (in terms of number of cops needed), while in other graphs, it is the second phase. Finally, we characterize those trees for which k cops are sufficient to guarantee capture of the robber for all l ≥ 1 .

A proper colouring is referred to as a Grundy colouring, or first-fit colouring if every vertex has a neighbour from each of the colour classes lower than its own. The Grundy number of a graph is the maximum k (number of colours) such that a Grundy colouring exists.In this note, we determine lower and upper bounds for the Grundy number of strong products of graphs, which lead to exact values for the product of some graph classes. We also provide an upper bound on the Grundy number of the strong product of n paths of length 2, which generalizes to an upper bound on the Grundy number of the strong product of n stars.