A note on deterministic zombies - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2021

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.
Fichier principal
Vignette du fichier
S0166218X21001827.pdf (278.18 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03473184 , version 1 (13-06-2023)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Bartier Valentin, Laurine Bénéteau, Marthe Bonamy, Xuan Hoang La, Jonathan Narboni. A note on deterministic zombies. Discrete Applied Mathematics, 2021, 301, pp.65-68. ⟨10.1016/j.dam.2021.05.001⟩. ⟨lirmm-03473184⟩
58 Consultations
2 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More