Cops and Robbers on Graphs of Bounded Diameter
Seyyed Aliasghar Hosseini, Fiachra Knox, Bojan Mohar · SIAM Journal on Discrete Mathematics · 2020
The game of Cops and Robbers is a well-known game played on graphs. In this paper, we consider the class of graphs of bounded diameter. We improve the strategy of cops and the previously used probabilistic method, which results in an improved upper bound for the cop number of graphs of bounded diameter. In particular, for graphs of diameter 4, we improve the upper bound from $n^{\frac{2}{3}+o(1)}$ to $n^{\frac{3}{5}+o(1)}$ and for diameter 3 from $n^{\frac{2}{3}+o(1)}$ to $n^{\frac{4}{7}+o(1)}$.