CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Graph Games

STEPHEN FINBOW, St Francis Xavier
Efficiency of Watchmen's Walks  [PDF]

We will discuss a method of measuring the efficiency of a watchmen's walk, where each vertex must be visited within a specified time interval and related results for small time intervals. Further explorations show every rooted tree with with relatively few leaves has a branch with a certain number of vertices and this can be used establish a conjecture of Dyer and Keeping.

SHANNON FITZPATRICK, University of Prince Edward Island
Copwin Edge Critical Graphs  [PDF]

In the game of Cops and Robber, a cop tries to apprehend a robber as they move along edges of a graph. A Copwin Edge Critical graph, with respect to edge addition (deletion), is a graph that is not Copwin, but the addition (deletion) of any edge results in a Copwin graph. In this talk, I will discuss properties of Copwin Edge Critical graphs and give a characterization of those that are also planar.

DAN HEFETZ, Queen Mary University of London
Fast embedding of spanning trees in biased Maker-Breaker games  [PDF]

We prove that there exist real numbers $\alpha, \varepsilon > 0$ such that, for sufficiently large $n$ and for every tree $T$ on $n$ vertices with maximum degree at most $n^{\varepsilon}$, when playing a $(1 : q)$ game on $E(K_n)$, Maker has a strategy to build a copy of $T$ for every $q \leq n^{\alpha}$. Moreover, we prove that Maker can do this within $n + o(n)$ moves which is clearly asymptotically optimal.

ABBAS MEHRABIAN, University of Waterloo
On a Generalization of Meyniel's Conjecture on the Cops and Robbers Game  [PDF]

We consider a variant of the Cops and Robbers game where the robber has speed $s$, and show that in this variant, the cop number of a connected $n$-vertex graph can be as large as $\Omega(n^{s/s+1})$. This improves the $\Omega(n^{{s-3/s-2}})$ lower bound of Frieze, Krivelevich, and Loh (Variations on Cops and Robbers, preprint, 2010). We also conjecture an upper bound of $O(n^{s/s+1})$ for the cop number, generalizing Meyniel's conjecture.

Joint work with Noga Alon.

SUZANNE SEAGER, Mount Saint Vincent University
Locating a Robber on a Graph  [PDF]

A cop chooses a vertex of a connected graph to probe; if she locates the robber she wins. Otherwise she receives the distance to him. The robber may move to any vertex adjacent to his location other than the probe. The cop wants to minimize the number of probes to win, while the robber wants to avoid detection. This is a synthesis of the cop-and-robber game with the metric dimension problem.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria