Journal of Combinatorics

Volume 13 (2022)

Number 1

Optimizing the trade-off between number of cops and capture time in Cops and Robbers

Pages: 79 – 203

DOI: https://dx.doi.org/10.4310/JOC.2022.v13.n1.a4

Authors

Anthony Bonato (Ryerson University, Toronto, Ontario, Canada)

Jane Breen (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Boris Brimkov (Department of Mathematics and Statistics, Slippery Rock University, Slippery Rock, Pennsylvania, U.S.A.)

Joshua Carlson (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A)

Sean English (Ryerson University, Toronto, Ontario, Canada)

Jesse Geneson (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Leslie Hogben (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.; and American Institute of Mathematics, San Jose, California, U.S.A.)

K. E. Perry (Department of Mathematics, University of Denver, Colorado, U.S.A.)

Carolyn Reinhart (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Abstract

The cop throttling number $\mathrm{th}_c (G)$ of a graph $G$ for the game of Cops and Robbers is the minimum of $k +\mathrm{capt}_k (G)$, where $k$ is the number of cops and $\mathrm{capt}_k (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 construct a family of graphs having $\mathrm{th}_c (G) = \Omega (n^{2/3})$, establish a sublinear upper bound on the cop throttling number, and show that the cop throttling number of chordal graphs is $O(\sqrt{n})$. We also introduce the product cop throttling number $\mathrm{th}^{\times}_c (G)$ as a parameter that minimizes the person-hours used by the cops. This parameter extends the notion of speed-up that has been studied in the context of parallel processing and network decontamination. 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$, $\mathrm{th}^{\times}_c (G) = 1+ \mathrm{rad}(G)$.

Keywords

Cops and Robbers, throttling, product throttling, chordal graph, graph searching

2010 Mathematics Subject Classification

05C57, 91A43

Full Text (PDF format)

Received 6 September 2019

Accepted 9 January 2021

Published 31 January 2022