Journal or Book Title
We consider the cop-throttling number of a graph G for the game of Cops and Robbers, which is defined to be the minimum of (k + capt(k)(G)), where k is the number of cops and capt(k)(G) is the minimum number of rounds needed for k cops to capture the robber on G over all possible games. We provide some tools for bounding the cop-throttling number, including showing that the positive semidefinite (PSD) throttling number, a variant of zero forcing throttling, is an upper bound for the cop-throttling number. We also characterize graphs having low cop-throttling number and investigate how large the cop-throttling number can be for a given graph. We consider trees, unicyclic graphs, incidence graphs of finite projective planes (a Meyniel extrema] family of graphs), a family of cop-win graphs with maximum capture time, grids, and hypercubes. All the upper bounds on the cop throttling number we obtain for families of graphs are O(root n).
Breen, Jane; Brimkov, Boris; Carlson, Joshua; Hogben, Leslie; Perry, K. E.; and Reinhart, Carolyn, "Throttling for the game of Cops and Robbers on graphs" (2018). Mathematics Publications. 204.
Available for download on Saturday, June 06, 2020