Cop throttling number: Bounds, values, and variants

Thumbnail Image
Date
2019-03-25
Authors
Bonato, Anthony
Breen, Jane
Brimkov, Boris
Carlson, Joshua
English, Sean
Geneson, Jesse
Hogben, Leslie
Perry, K. E.
Reinhart, Carolyn
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

The cop throttling number thc(G) of a graph G for the game of Cops and Robbers is the minimum of k+captk(G), where k is the number of cops and captk(G) is the minimum number of rounds needed for k cops to capture the robber on G over all possible games in which both players play optimally. In this paper, we answer in the negative a question from [Breen et al., Throttling for the game of Cops and Robbers on graphs, {\em Discrete Math.}, 341 (2018) 2418--2430.] about whether the cop throttling number of any graph is O(n−−√) by constructing a family of graphs having thc(G)=Ω(n2/3). We establish a sublinear upper bound on the cop throttling number and show that the cop throttling number of chordal graphs is O(n−−√). We also introduce the product cop throttling number th×c(G) as a parameter that minimizes the person-hours used by the cops. We establish bounds on the product cop throttling number in terms of the cop throttling number, characterize graphs with low product cop throttling number, and show that for a chordal graph G, th×c(G)=1+rad(G).

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article
Comments

This is a pre-print of the article Bonato, Anthony, Jane Breen, Boris Brimkov, Joshua Carlson, Sean English, Jesse Geneson, Leslie Hogben, K. E. Perry, and Carolyn Reinhart. "Cop throttling number: Bounds, values, and variants." arXiv preprint arXiv:1903.10087v1 (2019). Posted with permission.

Rights Statement
Copyright
Tue Jan 01 00:00:00 UTC 2019
Funding
DOI
Supplemental Resources
Collections