Skip to main content
Article
Throttling for the game of Cops and Robbers on graphs
Discrete Mathematics
  • Jane Breen, University of Manitoba
  • Boris Brimkov, Rice University
  • Joshua Carlson, Iowa State University
  • Leslie Hogben, Iowa State University and American Institute of Mathematics
  • K. E. Perry, University of Denver
  • Carolyn Reinhart, Iowa State University
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
9-1-2018
DOI
10.1016/j.disc.2018.05.017
Abstract

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).

Comments

This is a manuscript of an article published as Breen, Jane, Boris Brimkov, Joshua Carlson, Leslie Hogben, K. E. Perry, and Carolyn Reinhart. "Throttling for the game of Cops and Robbers on graphs." Discrete Mathematics 341, no. 9 (2018): 2418-2430. DOI: 10.1016/j.disc.2018.05.017. Posted with permission.

Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier B.V.
Language
en
File Format
application/pdf
Citation Information
Jane Breen, Boris Brimkov, Joshua Carlson, Leslie Hogben, et al.. "Throttling for the game of Cops and Robbers on graphs" Discrete Mathematics Vol. 341 Iss. 9 (2018) p. 2418 - 2430
Available at: http://works.bepress.com/leslie-hogben/90/