2018/06/12 by Fitzpatrick, Shannon L.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1806.04628
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 \lceil 2n/3 \rceil. 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.