A deterministic version of the game of zombies and survivors on graphs

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.