A note on deterministic zombies - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Applied Mathematics Year : 2021

A note on deterministic zombies

Abstract

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
Origin Files produced by the author(s)

Dates and versions

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

Licence

Identifiers

Cite

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⟩
65 View
6 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More