A note on deterministic zombies
Résumé
Zombies and Survivor is a variant of the well-studied game of Cops and Robbers where the zombies (cops) can only move closer to the survivor (robber). We consider the deterministic version of the game where a zombie can choose their path if multiple options are available. Similar to the cop number, the zombie number of a graph is the minimum number of zombies required to capture the survivor. In this short note, we solve a question by Fitzpatrick et al., proving that the zombie number of the Cartesian product of two graphs is at most the sum of their zombie numbers. We also give a simple graph family with cop number 2 and an arbitrarily large zombie number.
Domaines
Combinatoire [math.CO]Origine | Fichiers produits par l'(les) auteur(s) |
---|