In many variants of the game of Cops and Robbers on graphs, multiple cops play against a single robber. In 2019, Cox and Sanaei introduced a variant of the game that gives the robber a more active role than simply evading the cop. In their version, the robber tries to damage as many vertices as possible and the cop attempts to minimize this damage. While the damage variant was originally studied with one cop and one robber, it was later extended to play with multiple cops by Carlson et. al in 2021. We take a different approach by studying the damage variant with multiple robbers against one cop. Specifically, we introduce the $s$-robber damage number of a graph and obtain a variety of bounds on this parameter. Applying these bounds, we determine the $s$-robber damage number for a variety of graph families and characterize graphs with extreme $2$-robber damage number.
翻译:在图表上的“警察”和“抢劫者”游戏的许多变体中,多个警察对一个强盗玩耍。2019年,考克斯和萨内伊引入了一个游戏变体,让强盗发挥比逃避警察更积极的作用。在他们的版本中,强盗试图破坏尽可能多的脊椎,而警察试图尽量减少这种破坏。虽然最初用一个警察和一个强盗来研究破坏变体,但后来Carlson等人在2021年又将其扩大到与多个强盗玩耍。我们采取了不同的方法,用多个强盗对一个强盗来研究破坏变体。具体地说,我们采用一个图的美元-强盗破坏数,并获得这个参数上的各种界限。运用这些界限,我们为各种图表家庭确定美元-强盗损害数,并用价值极高的2美元-强盗破坏数来描述图表。