Graph Searching Games  Part II
Org:
Anthony Bonato (Ryerson University) and
Danielle Cox (Mount Saint Vincent University)
[
PDF]
 BILL KINNERSLEY, University of Rhode Island
Cops and Lawless Robbers [PDF]

Cops and Robbers on undirected graphs has been throughly studied, but frustratingly little is known about Cops and Robbers on directed graphs. In hopes of rectifying this, we introduce a new variant of Cops and Robbers, which we refer to as Cops and Lawless Robbers. In this variant, played on a directed graph, the cops must respect the directions of the edges, but the robber need not. We study this game on several classes of directed graphs, including planar directed graphs, outerplanar directed graphs, and Cartesian products of arborescences and directed cycles. This is joint work with Eric Peterson.
 KERRY OJAKIAN, Bronx Community College (C.U.N.Y.)
Graphs that are copwin, but not zombiewin [PDF]

In the zombie variant of the game of cops and robbers, the cops must always move closer to the robber on their turn. We define copwin graphs in the usual way: graphs on which one cop can win. We define zombiewin graphs as follows: graphs on which one zombie can win from any start position. We say that a graph is copzombie gap if it is copwin, but not zombiewin. We investigate a number of questions related to the copzombie gap graphs, such as describing the minimum copzombie gap graphs.
 PAWEL PRALAT, Ryerson University
Zero Forcing Number of Random Regular Graphs [PDF]

The zero forcing process is an iterative graph colouring process in which at each time step a coloured vertex with a single uncoloured neighbour can force this neighbour to become coloured. A zero forcing set of a graph is an initial set of coloured vertices that can eventually force the entire graph to be coloured. The zero forcing number is the size of the smallest zero forcing set. We explore the zero forcing number for random regular graphs. In particular, we propose and analyze a degreegreedy algorithm for finding small zero forcing sets using the differential equations method.
 LADISLAV STACHO, Simon Fraser University
Efficient Periodic Graph Traversal on Graphs with a Given Rotation System [PDF]

We review problem of periodicgraphtraversal, which is to design an agent $A$ and portlabelingscheme $L$ such that $A$ (using $L$) performs on any undirected graph an infinite walk that periodically visits all vertices. The goal is to minimize revisittime of any vertex over all graphs on $n$ vertices. It is an open problem to show that when $L$ is limited to a permutation at every vertex, this time is at most $2n2$.
In this talk, we sketch a proof of an affirmative answer to the problem under the assumption that the input graph is given with a rotation system.