

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。