Graph Searching Games - Part II
Org: Anthony Bonato
(Ryerson University) et Danielle Cox
(Mount Saint Vincent University)
- 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 cop-win, but not zombie-win [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 cop-win graphs in the usual way: graphs on which one cop can win. We define zombie-win graphs as follows: graphs on which one zombie can win from any start position. We say that a graph is cop-zombie gap if it is cop-win, but not zombie-win. We investigate a number of questions related to the cop-zombie gap graphs, such as describing the minimum cop-zombie 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 degree-greedy 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 periodic-graph-traversal, which is to design an agent $A$ and port-labeling-scheme $L$ such that $A$ (using $L$) performs on any undirected graph an infinite walk that periodically visits all vertices. The goal is to minimize revisit-time 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 $2n-2$.
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.