A Sublinear Bound on the Cop Throttling Number of a Graph

Abstract

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)\le \frac{(2+o(1))n\sqrt{W(\log (n))}}{\sqrt{\log (n)}},$ where $W=W(x)$ is the Lambert W function.

arXiv comment6 pages

References in corpus (1)

• Throttling positive semidefinite zero forcing propagation time on graphs