Cops and Robbers on Graphs (C & R) is a vertex-to-vertex pursuit game played on
graphs first introduced by Quilliot (in 1978) and Nowakowski (in 1983). The cop
player starts the game by choosing a set of vertices which will be the cops’ starting
positions. The robber player responds by choosing its own start vertex. On each
player’s turn, the player may move its tokens to adjacent vertices. The cops win
if the robber is captured (they occupy the same vertex). The robber wins if it can
avoid capture indefinitely. The question, then, is to determine the smallest number
of cops required to guarantee the robber will be captured. A variation of C & R called
Zombies and Survivors (Z & S) was recently proposed and studied by Fitzpatrick.
Z & S is the same as C & R with the added twist that the zombies are required to
move closer to the survivor (by following a shortest path from the zombie to the
survivor). Whenever multiple shortest paths exist, the zombies are free to choose
which one to follow. As in C & R, we are interested in the minimum number of
zombies required to guarantee the survivor will be caught. Chapter 1 summarizes
important results in vertex-pursuit games. In Chapter 2 we give an example of a
planar graph where 3 zombies always lose, whereas Aigner and Fromme showed
in 1984 that three cops have a winning strategy on planar graphs. In Chapter 3 we
show how two zombies can win on a cycle with one chord.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/41077 |
| Date | 22 September 2020 |
| Creators | Faubert, Joël |
| Contributors | De Carufel, Jean-Lou |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0122 seconds