A Sublinear Bound on the Cop Throttling Number of a Graph
Anthony Bonato, Sean E. English · arXiv (Cornell University) · 2019
We provide a sublinear bound on the cop throttling number of a connected graph. Related to the graph searching game Cops and Robbers, the cop throttling number, written $\mathrm{th}_c(G)$, is given by $\mathrm{th}_c(G)=\min_k\{k+\mathrm{capt}_k(G)\}$, in which $\mathrm{capt}_k(G)$ is the $k$-capture time, or the length of a game of Cops and Robbers with $k$ cops on the graph $G$, assuming both players play optimally. No general sublinear bound was known on the cop throttling number of a connected graph. Towards a question asked by Breen et al., we prove that $\mathrm{th}_c(G)\leq \frac{(2+o(1))n\sqrt{W(\log(n))}}{\sqrt{\log(n)}},$ where $W=W(x)$ is the Lambert W function.