Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949958 | Discrete Applied Mathematics | 2016 | 12 Pages |
Abstract
We consider a variant of the pursuit-evasion game Cops and Robber, called Zombies and Survivors. The zombies, being of limited intelligence, have a very simple objective at each round: move closer to a survivor. The zombies capture a survivor if one of the zombies moves onto the same vertex as a survivor. The survivor's objective is to avoid capture for as long as possible, hopefully indefinitely. Because there may be multiple geodesics, or shortest paths, joining a zombie and its nearest survivor, the game can be considered from a probabilistic or deterministic approach. In this paper, we consider a deterministic approach to the game. In particular, we consider the worst case for the survivors; whenever the zombies have more than one possible move, they choose one that works to their advantage. This includes choice of initial position, and choosing which geodesic to move along if more than one is available. In other words, the zombies play intelligently, subject to the constraint that each zombie must move along a geodesic between itself and the nearest survivor. The zombie number of a graph G is the minimum number of zombies required to capture the survivor on G. We determine the zombie number for various graphs, examine the relationship between the zombie number and cop number of a graph, and describe some distinctions from Cops and Robber.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
S.L. Fitzpatrick, J. Howell, M.E. Messinger, D.A. Pike,