A Sublinear Bound on the Cop Throttling Number of a Graph

MaRDI QIDQ6313071zbMATH OpenFDO

Authors Anthony Bonato, Sean English

Publication date 25 January 2019

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57)

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)=mi{n}_{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)leqfrac(2+o(1))nsqrtW(log(n))sqrtlog(n),$ where $W=W(x)$ is the Lambert W function.

This page was built for publication: A Sublinear Bound on the Cop Throttling Number of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6313071)