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 .

For a fixed integer t, a set of vertices B of a graph G is a t-limited packing of G provided that the closed neighbourhood of any vertex in G contains at most t elements of B. The size of a largest possible t-limited packing in G is denoted Lt(G) and is the t-limited packing number of G. In this paper, we investigate the 2-limited packing number of Cartesian products of paths. We show that for fixed k the difference L2(PkPn)L2(PkPn1) is eventually periodic as a function of n, and thereby give closed formulas for L2(PkPn), k=1,2,,5. The techniques we use are suitable for establishing other types of packing and domination numbers for Cartesian products of paths and, more generally, for graphs of the form HPn.

We introduce a new variant of the game of Cops and Robbers played on graphs, where the robber is invisible unless outside the neighbor set of a cop. The hyperopic cop number is the corresponding analogue of the cop number, and we investigate bounds and other properties of this parameter. We characterize the cop-win graphs for this variant, along with graphs with the largest possible hyperopic cop number. We analyze the cases of graphs with diameter 2 or at least 3, focusing on when the hyperopic cop number is at most one greater than the cop number. We show that for planar graphs, as with the usual cop number, the hyperopic cop number is at most 3. The hyperopic cop number is considered for countable graphs, and it is shown that for connected chains of graphs, the hyperopic cop density can be any real number in [ 0 , 1 / 2 ] .

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.

We give two characterizations of the graphs on which k cops have a winning strategy in the game of Cops and Robber. One of these is in terms of an order relation, and one is in terms of a vertex ordering. Both generalize characterizations known for the case k=1.

In this version of the Cops and Robber game, the cops move in tandems, or pairs, such that they are at distance at most one after every move. We present a recognition theorem for tandem-win graphs, and a characterization of triangle-free tandem-win graphs.