Efficient attack sequences in m-eternal dominationwith Jan Matyáš Křišťan and Tomáš Valla
We are given a graph and a number of guards to defend it against a sequence of vertex attacks. Defender controls the guards and may move every guard by at most one edge after each attack. After his move the attacked vertex must be occupied by a guard, otherwise the attacked wins. Defender wins if he has a strategy that defends the graph indefinitely.
We investigate this problem for trees where the optimal strategy was already known. However, if the defender has insufficient number of guards, then how can we attack efficiently? We analyze the worst case where the defender is missing a single guard to be able to defend indefinitely.
We show a polynomial optimum attack strategy via induction on depth based on evaluating potential for each subtree. The number of necessary attacks is roughly the depth of the tree when rooted in the centroid.