论文标题
在多机攻击数字上
On the Multi-Robber Damage Number
论文作者
论文摘要
我们在图表上研究了警察和强盗游戏的一种变体，其中强盗损坏了访问的顶点，旨在最大程度地增加受损顶点的数量。对于与$ S $抢劫犯的一名警察，卡尔森，哈罗兰和赖因哈特对一名警察的猜想是，一旦基本图的最高程度至少为$ \ binom {s} {2} {2} {2} + 2 $，警察可以节省三个顶点。 我们能够验证猜想，并证明一旦添加了基本图不含三角形的假设，就会紧张。我们还没有那个假设来研究游戏，以完全普遍性地说明了猜想，并试图找到基本图的最大最大程度，以确保警察可以为$ s $抢劫者保存三个顶点。我们表明，这个数字在$ 2 \ binom {s} {2} -3 $和$ 2 \ binom {s} {2} + 1 $之间。 此外，在比赛以前已经与一名警察和多个强盗一起研究之后，以及一名强盗和多个警察，我们用两名警察和两名强盗开始对比赛的研究。在基本图为周期的情况下，我们确定了损坏的顶点的确切数量。另外，当基本图是一条路径时，我们提供的边界会因添加剂常数而不同。
We study a variant of the Cops and Robbers game on graphs in which the robbers damage the visited vertices, aiming to maximize the number of damaged vertices. For that game with one cop against $s$ robbers a conjecture was made by Carlson, Halloran and Reinhart that the cop can save three vertices from being damaged as soon as the maximum degree of the base graph is at least $\binom{s}{2} + 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 is between $2\binom{s}{2} - 3$ and $2\binom{s}{2} + 1$. Furthermore, after the game has been previously studied with one cop and multiple robbers, as well as with one robber and multiple cops, we initiate the study of the game with two cops and two robbers. In the case when the base graph is a cycle we determine the exact number of damaged vertices. Additionally, when the base graph is a path we provide bounds that differ by an additive constant.
