Exploring the damage number of a graph

Abstract

Cops and Robbers is a well-studied 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 the damage number of a graph, in which the original goal of the players in Cops and Robbers is altered. In this game, the robber's goal is to visit the maximum number of unique vertices in a graph while the cops' goal is to minimize this number. Although the damage number of a graph can be studied with any number of cops, we will consider the game with a single cop and robber. We present new results which characterize graphs with damage number one, provide an improved lower bound on the damage number for any graph, and determine the exact value for the damage number of graph joins. Following this, we provide a relationship between cut-sets and the damage number by defining a new graph property, star cut-sets, and explore this property through cactus graphs.