CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Pursuit-Evasion Games on Graphs
Org: Bill Kinnersley (University of Rhode Island)

DANNY DYER, Memorial University
Watching Halin graphs  [PDF]

The Watchman problem involves finding a closed dominating walk in a graph on minimum length. This is known to be easy in trees. This makes Halin graphs (formed from joining the leaves of a planar embedding of a tree in a cycle) a natural family of graphs to consider. We consider some recent progress on this family. Joint work with Jared Howell and Shane Andrews.

Cops and Robbers on Oriented Grids  [PDF]

Cops and Robbers is a well-known pursuit game on graphs. The main question in this game is to determine the minimum number of cops that can guarantee to capture the robber on the given graph.

This problem has been widely studied for the case of undirected graphs, but very little attention has been given to finding the cop number of digraphs. In this talk we present results about the cop number of a family of directed graphs embedded on the torus.

BILL KINNERSLEY, University of Rhode Island
Bounds on the Capture Time of Graphs  [PDF]

The study of Cops and Robbers has historically focused on the cop number, the minimum number of cops needed to capture a robber on some graph. Less attention has been given to the capture time, the minimum number of turns needed for the cops to win. It is straightforward to show that every $n$-vertex graph with cop number $k$ has capture time $O(n^{k+1})$, but constructing graphs with large capture time has proved difficult. In this talk we show that, perhaps surprisingly, the easy upper bound of $O(n^{k+1})$ is asymptotically tight.

NATASHA KOMAROV, St. Lawrence University
Using spotlights to find a robber  [PDF]

We consider a pursuit game which models a cop using a spotlight (or spotlights) to search for a robber on a dark graph. A spotlight can point at any one vertex at any time (regardless of adjacency) but the cop cannot see the robber unless he occupies an illuminated vertex. We characterize the graphs on which one spotlight is sufficient in order to guarantee capture of the robber in bounded time and discuss a surprising optimal strategy for the cop. We will also discuss (tight) bounds on the number of spotlights required to find the robber on general graphs.

KERRY OJAKIAN, Bronx Community College (C.U.N.Y.)
Extremal Cop-Win Graphs  [PDF]

For a cop-win graph, the capture time is the number of moves required by one cop to catch the robber. We consider graphs that are extremal (or almost extremal) with respect to capture time, i.e. their capture time is as large as possible relative to their order, characterizing such graphs (thus reproving an old result and proving a new result). Our new approach involves associating graphs to vectors (i.e. finite lists of integers) and then partially determining which vectors can be realized by some graph. We leave fully characterizing these vectors as an open question.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology