On the Multi-Robber Damage Number
share
We study a variant of the Cops and Robbers game on graphs in which the robbers damage the visited vertices, aiming to maximise the number of damaged vertices. For that game with one cop against s robbers a conjecture was made in <cit.> that the cop can save three vertices from being damaged as soon as the maximum degree of the base graph is at least s2 + 2. We are able to verify the conjecture and prove that it is tight once we add the assumption that the base graph is triangle-free. We also study the game without that assumption, disproving the conjecture in full generality and further attempting to locate the smallest maximum degree of a base graph which guarantees that the cop can save three vertices against s robbers. We show that this number if between 2s2 - 3 and 2s2 + 1.
READ FULL TEXT