The Zombie Damage Number of a Graph

Abstract

In the damage variant of Cops and Robber, the \emph{damage number} \(\dmg(G)\) is the number of distinct vertices damaged by the robber under optimal play, with one cop minimizing and the robber maximizing this number. We introduce the \emph{zombie damage number} \(\zdmg(G)\), obtained by requiring the pursuer to move at every turn along a shortest path toward the survivor. The parameter therefore measures the cost of geodesic pursuit when the objective is containment rather than capture alone. We prove that \(\dmg(G)\leq\zdmg(G)\) and characterize the graphs with \(\zdmg(G)=0\). Geodesic pursuit incurs no additional damage on trees, and we determine the parameter exactly for paths, cycles, split graphs, and complete multipartite graphs. In particular, \(\zdmg(C_n)=n\) for \(n\geq5\), while \(\zdmg(K_{n_1,\ldots,n_k})=n_1+n_2-2\) when \(n_i\geq2\) for every \(i\). We also develop a nonbacktracking trace argument for sparse graphs. If \(G\) is connected, \(δ(G)\geq2\), and \(g(G)\geq5\), then every vertex is damaged, and hence \(\zdmg(G)=n(G)\). The same argument gives the sharp bound \(\zdmg(G)\geq g(G)\) for every connected graph of finite girth at least five. It follows that fully subdividing each edge of a connected graph of minimum degree at least two produces a graph with maximum zombie damage. These results yield an unbounded separation from the ordinary damage number. Most of the questions leading to these results, as well as the open conjectures, arose through \textsc{Theo-Conjecture}, an advisor-supervised discovery loop combining automated conjecturing, exact computation, language-model-assisted exploration, and human mathematical judgment.

Disclosure

“tion when triangles and quadrilaterals are absent. Computer assistance was used during the formulation of questions. The computer system Theo-Conjecture compared exact values on finite graphs and proposed relations for further study. A language model helped interpret the candidates and suggest counterexample searches. The author selected the problems, assessed their significance, and developed and checked the proofs. This use of computation continues the graph-theoretic practice of mac”

PDF page 3

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:56:54.704259Z

Structural counts