Réunion d'été 2009 de la SMC et de la SCHPM
Université Memorial de Terre-Neuve, St. John's (Terre Neuve), 6 - 8 juin, 2009

Graph Searching
Org: Anthony Bonato (Ryerson), Danny Dyer (Memorial) et Gary McGillivray (Victoria)

ANTHONY BONATO, Ryerson University
Cops and Robbers from a Distance

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.

EHSAN CHINIFOROOSHAN, Concordia University, Montreal, Quebec, Canada
When cops and robbers do not move on the same graph

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.

NANCY CLARKE, Acadia University, Wolfville, Nova Scotia
Edge-Critical Cops and Robber

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.

DANNY DYER, Memorial

ART FINBOW, Saint Mary's University
Designing Resilient Graphs

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.

STEPHEN FINBOW, St. Francis Xavier
Firefighting on K4 minor free graphs

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 K4-minor free graphs.

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

BERT HARTNELL, Saint Mary's University, Halifax, NS
On Scheduling the Watchmen

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.

JAN KRATOCHVIL, Charles University, Malostranske namesti 25, 11800 Praha 1, Czech Republic
Who's gonna catch the Robber? And when?

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.

MARGARET-ELLEN MESSINGER, University of Montana, Missoula, MT 59812
Parallel Cleaning of a Network with Brushes

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.

RICHARD NOWAKOWSKI, Department of Mathematics and Statistics Dalhousie University
Cleaning with Sequential Brushes

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.

PAWEL PRALAT, Dalhousie University
Cleaning random d-regular graphs with brooms

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) ).

BOTING YANG, University of Regina
Guarding graphs with small diameter

We discuss the guarding game introduced by Fomin et al. when the cop region is a specific graph class. We show that the guarding number can be found in linear time when the cop region is a complete bipartite graph and the guarding problem is NP-hard when the cop region is a graph of diameter two. We give a 2-approximation algorithm for this case. We prove that the guarding problem is NP-hard when the cop region is a split graph and we introduce a new variant of the guarding game, namely, cops have speed two. The speed two variant of the guarding game is solvable in linear time when the cop region is a split graph but it is NP-hard when the cop region is a graph of diameter 3 and we give a 2-approximation algorithm for this case.

Joint work with Rodica Mihai.


l'Université Memorial de Terre-Neuve    AARMS: Atlantic Association for Research in the Mathematical Sciences    Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Réseau canadien de recherche sur le langage et l'alphabétisation

© Société mathématique du Canada :