Simona Gagarova

Exploring the Multi-Robber Damage Number

Started July 1, 2024

Abstract or project description

Cops and Robbers is a pursuit-evasion game, where a set of cops aims to capture a robber on a graph while the robber attempts to avoid capture indefinitely. We consider a version of the game where multiple robbers aim to visit as many vertices of the graph as possible and damage them, while the cop attempts to minimize this damage. We characterize the graphs with the smallest possible damage number for s > 2. Following this, we determine the exact value of the s-robber damage number for wheel graphs, accordion graphs, complete bipartite graphs, and Hn. For k > 3, we examine the restrictions on the maximum degree of a graph G in which the cop can always save k vertices. We establish that for triangle-free graphs, the maximum degree must be at least s(s-1)/2 +k-1. For graphs that are not triangle-free and for k ≤ s(s-1), we provide upper and lower bounds on the smallest maximum degree necessary for the cop to save k vertices.