The multi-robber damage conjecture on saving three vertices

Let GG be a graph with maximum degree Δ(G)\Delta(G), and let ss be a positive integer. In the one-cop, ss-robber damage game, the cop saves kk vertices if the optimal damage satisfies dmg(G;s)V(G)k\operatorname{dmg}(G;s)\leq |V(G)|-k.

Multi-robber damage conjecture. For all s>2s>2, if

Δ(G)(s2)+2,\Delta(G)\geq \binom{s}{2}+2,

then the cop can save three vertices against ss robbers.

For two robbers, the corresponding result is known under the weaker condition Δ(G)3\Delta(G)\geq 3. The conjecture proposes a sufficient maximum-degree condition for saving three vertices with more than two robbers; its status is not established in the supplied text.

Sources & referencesView supporting material

Primary source

Miloš Stojaković and Lasse Wulf, “On the Multi-Robber Damage Number”, arXiv:2209.10965 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.