Papers › The damage throttling number of a graph
The damage throttling number of a graph
Joshua Carlson, Robin Eagleton, Jesse Geneson, John Petrucci, Carolyn Reinhart, Preetul Sen
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 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 th_d(G) = Ω(n^(2/3)).
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections