CMS/SMC
CanaDAM 2011
University of Victoria, May 31 - June 3, 2011 www.cms.math.ca//2011
       

Graph Searching
Org: Anthony Bonato (Ryerson University), Nancy Clarke (Acadia University) and Boting Yang (University of Regina)
[PDF]

NANCY CLARKE, Acadia University
Characterizations of $k$-copwin graphs  [PDF]

We give two characterizations of the graphs on which $k$ cops have a winning strategy in the Cops and Robber game. These generalize the corresponding characterizations in the one cop case. In particular, we give a relational characterization of $k$-copwin graphs, for all finite $k$, and a vertex elimination order characterization of such graphs. Our results hold for variations of the game and some extend to infinite graphs. This is joint work with Gary MacGillivray.

DANNY DYER, Memorial University of Newfoundland
Fast searching graphs with few searchers  [PDF]

The edge search number of a graph is defined as the minimum number of cops needed to cast a fast invisible robber that may rest on a graph's vertices or edges. The fast search number is the minimum number of cops needed to capture such a robber in as few moves as possible. Paralleling the development of the edge search number, we will discuss graphs that require at most 3 cops to guarantee capture.

GEŇA HAHN, University of Montreal
Cops-and-robbers revisited  [PDF]

We suggest a generalization of the original Nowakowski-Quilliot-Winkler game that the players can play on distinct graphs. This allows for an easier introduction of constraints on the players' moves and so leads to a host of questions.

GARY MACGILLIVRAY, University of Victoria
A characterization of infinite cop-win graphs  [PDF]

There are essentially two characterizations of finite cop-win graphs. One is in terms of a relation defined on the vertex set, and the other is in terms of a vertex ordering. The first characterization holds unchanged for infinite graphs; the second does not. We show that, if the second characterization is reformulated in terms of a sequence of retractions that each fix all but one vertex, then it also holds unchanged for infinite graphs.

RICHARD NOWAKOWSKI, Dalhousie University
Cops and Robber with different edges sets  [PDF]

In "Cops and Robber", the cops are assumed to obey the rules and the Robber not. This suggests that they should play on different edges sets. I'll present what little is known and that only covers certain situations, specifically, (a) the different edges sets are obtained from the edges of products; (b) complementary sets of edges. There are more questions than answers.


Handling of online submissions has been provided by the CMS.

Event Sponsors

Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Victoria