论文标题
图表的损坏数量
The damage throttling number of a graph
论文作者
论文摘要
Breen等人在2018年推出的图形的COP节流数量优化了所使用的警察数量与在警察和强盗游戏中捕获强盗所需的回合数量之间的平衡。 2019年，考克斯（Cox）和萨耶伊（Sanaei）研究了一系列警察和强盗，强盗试图占据（或损害）尽可能多的顶点，而警察试图最大程度地减少这种损害。在他们的论文中，他们研究了在给定图表$ g $上玩的所有游戏中，强盗损坏的最小顶点数量，称为$ g $的损失数量。我们介绍了称为图的损坏节流数的自然参数，表示为$ \ permatatorName {th} _d（g）$，该$优化了所使用的警察数量与图表中损坏的顶点之间的余额。为此，我们将$ k $ damage号码的定义正式化，该定义将损失号码扩展到了$ k $ cops玩的游戏。我们表明，损坏的节流和警察节流分享了许多属性，但它们表现出有趣的差异。我们证明，损坏的节流数的限制在上面的限制比警察限制数少。给出了无限的例子和非范围内的习惯。我们还找到了一个无限的连接图表$ g $的订单$ n $，$ \ permatatorName {th} _d（g）=ω（n^{2/3}）$。
The cop throttling number of a graph, introduced in 2018 by Breen et al., optimizes the balance between the number of cops used and the number of rounds required to catch the robber in a game of Cops and Robbers. In 2019, Cox and Sanaei studied a variant of Cops and Robbers in which the robber tries to occupy (or damage) as many vertices as possible and the cop tries to minimize this damage. In their paper, they study the minimum number of vertices damaged by the robber over all games played on a given graph $G$, called the damage number of $G$. We introduce the natural parameter called the damage throttling number of a graph, denoted $\operatorname{th}_d(G)$, which optimizes the balance between the number of cops used and the number of vertices damaged in the graph. To this end, we formalize the definition of $k$-damage number, which extends the damage number to games played with $k$ cops. We show that damage throttling and cop throttling share many properties, yet they exhibit interesting differences. We prove that the damage throttling number is tightly bounded above by one less than the cop throttling number. Infinite families of examples and non-examples of tightness in this bound are given. We also find an infinite family of connected graphs $G$ of order $n$ for which $\operatorname{th}_d(G) = Ω(n^{2/3})$.
