In vertex pursuit games played on graphs such as Cops and Robbers, the cops must occupy the node of the robber to win. We present results on scenarios where the cops win if they are some prescribed distance from the robber. We study this new game-distance k Cops and Robber-from algorithmic, structural, and probabilistic perspectives.

We consider the game in which cops can move along the edges of a graph G and the robber can move along the edges of another graph H such that V(G) = V(H). We give motivations for considering this new game and partial results.

We consider edge-critical graphs when playing Cops and Robber. Specifically, we look at those graphs whose copnumber changes from one to two when any edge is added, deleted, subdivided or contracted. We characterize all such sets, showing that they are empty, trees, all 2-edge-connected graphs and empty, respectively. We also consider those graphs which change from copnumber two to one when any edge is added, and give a characterization in the k-regular case.

This is joint work with S. L. Fitzpatrick, A. Hill, and R. J. Nowakowski.

Intrusions occur at a set S of f vertices in a connected simple graph G. Each of d defenders protects one node that is not yet corrupted. The "infection" then spreads to a set of neighbouring unprotected nodes. The intruders and defenders take turns until some stopping condition is true.

For a fixed positive integer n, we consider the problem of constructing a graph G that is optimal in the following sense: the expected damage resulting from a random attack by a set of f intruders on G is minimum for graphs of order n.

Let G be a connected graph with n ³ 2 vertices. Suppose that a fire breaks out at a vertex v of G and a firefighter then protects a vertex not yet on fire. Afterwards, the fire spreads to all its unprotected neighbours in each time interval. The fire and firefighter take turns until the fire can no longer spread.

The survival rate of G can be thought of as the expected proportion of vertices the firefighter can save when a fire breaks out at a random vertex. The discharging method is used to obtain results on the survival rate of K₄-minor free graphs.

This is joint work with P. Wang and W. Wang.

Given a network G and an integer t, we would like to determine the minimum number of watchpersons required, and their routes (rounds), so that the maximum time that any node is not monitored (no watchperson in its closed neighbourhood) is t. As this is difficult in general we will attempt to characterize some classes of graphs for which it is easy to do.

Pursuit games in graphs have attracted a lot of attention both for their practical motivation and theoretical impact, as many of their variants relate to various width parameters of graphs. We will survey recent results on a Cops & Robber game introduced in 1980s by Nowakowski-Winkler, and by Quilliot.

In this game two players take turns, one moving a group of cops along edges of the graph, the other one moving the robber. The robber gets caught if at some moment he/she is standing in the same vertex as one of the cops. The cops win the game when they catch the robber, the robber wins if he/she can avoid capture indefinitely.

We consider the questions of how many cops are needed to catch the robber in a given graph, or how many steps they need for it. Computational complexity of these questions is studied, as well as extremal results for particular graph classes. Interesting results have been obtained when the speed of the robber is allowed to be higher than the speed of the cops. We conclude with a number of open problems.

We consider the process of cleaning a network where at each time step, all vertices that have at least as many brushes as incident, contaminated edges, send brushes down these edges and remove them from the network. An added condition is that, because of the contamination model used, the final configuration must be the initial configuration of another cleaning of the network. We find the minimum number of brushes required for some classes of graphs; and for all networks when all edges must be cleaned on each step. Finally, we give bounds on the number of brushes required for complete networks.

This is joint work with S. Gaspers, R. J. Nowakowski, P. Pralat.

Following the decontamination metaphor for searching a graph, we introduce a cleaning process, which is related to both the chip-firing game and edge searching. The model presented is one where the edges are continually re-contaminated, say by algae, so that cleaning is regarded as an on-going process. We show that this is possible with the least number of brushes if the vertices are fired sequentially. We also present bounds for the least number of brushes required to clean graphs in general and some specific families of graphs.

A model for cleaning a graph with brushes was recently introduced. We consider the maximum number of brushes that can be used to clean d-regular graphs in this model, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm (for fixed d).

We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d+1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2Ö{d ln2})/4 brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the maximum possible number of brushes that can be used to clean a random d-regular graph on n vertices is asymptotically almost surely [(n)/4] ( d+O(Öd) ).