The game of zombies and survivors on cartesian products of graphs

We consider the game of Zombies and Survivors as introduced by Fitzpatrick, Howell, Messinger and Pike (2016) This is a variation of the game Cops and Robber where the zombies (in the cops' role) are of limited intelligence and will always choose to move closer to a survivor (who takes on the robber's role). The zombie number of a graph is defined to be the minimum number of zombies required to guarantee the capture of a survivor on the graph. In this paper, we show that the zombie number of the Cartesian product of n non-trivial trees is exactly ⌈2n/3⌉. This settles a conjecture by Fitzpatrick et. al. (2016) that this is the zombie number for the n-dimensional hypercube. In proving this result, we also discuss other variations of Cops and Robber involving active and flexible players.