The multi-robber damage conjecture on saving three vertices

About 4 years old · traced to

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.

References

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.