Zombie number invariance under leaf attachment

Question 4.1 · arXiv:2008.03587

arXiv Question high confidence— first stated 2021-06-03

Authors: Valentin Bartier, Laurine Bénéteau, Marthe Bonamy, Hoang La, Jonathan Narboni

Status open high confidence

Question 4.1 from arXiv:2008.03587 asks whether adding pendant (degree-1) vertices to a graph G always leaves the zombie number unchanged, i.e., z(G') = z(G). No resolution of this question has been found in the literature since the paper's publication in Discrete Applied Mathematics (2021). Follow-up work on deterministic zombies (e.g., arXiv:2204.11926 on lazy zombies, and a 2022 IWOCA chapter on zombie numbers of various graph classes) does not appear to address this specific question about pendant vertices.

Reviewer notes. No follow-up addressing the pendant-vertex invariance question was found across three targeted searches. Related papers (arXiv:2204.11926 on lazy zombies; SpringerLink chapter 10.1007/978-3-031-20624-5_32 on zombie numbers of graph classes) focus on other aspects of the zombie number. The conjecture is recent (2021) and the absence of evidence is consistent with it remaining open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. For every graph $G$, and for a graph $G'$ obtained from $G$ by successively adding vertices of degree 1, does it always hold that $z(G') = z(G)$?

Context

This question asks whether attaching pendant vertices (leaves) to a graph leaves its zombie number unchanged. It can be interpreted as asking whether zombies can benefit from waiting at a designated position before activating at the start of the game.

Source paper

A note on deterministic zombies
Valentin Bartier, Laurine Bénéteau, Marthe Bonamy, Hoang La, Jonathan Narboni · 2021-06-03
https://arxiv.org/abs/2008.03587 PDF source