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

• DOI: 10.48550/arxiv.1903.10087
• Publication Date: 2019-01-01
• Authors: Anthony Bonato; Jane Breen; Boris Brimkov; Joshua M. Carlson; Sean English; Jesse Geneson; Leslie Hogben; K. E. Perry; Carolyn Reinhart
• Keywords: Bandwidth throttling; Throttle; Sublinear function

The cop throttling number $th_c(G)$ of a graph $G$ for the game Cops and Robbers is minimum $k + capt_k(G)$, where $k$ cops $capt_k(G)$ rounds needed to capture robber on over all possible games in which both players play optimally. In this paper, we construct family graphs having $th_c(G)= \Omega(n^{2/3})$, establish sublinear upper bound number, show that chordal $O(\sqrt{n})$. We also introduce product $th_c^{\times}(G)$ as parameter minimizes person-hours used by cops. This extends notion speed-up has been studied context parallel processing network decontamination. bounds terms characterize with low $G$, $th_c^{\times}=1+rad(G)$.