Bulletin of the
Korean Mathematical Society BKMS

We discuss two unrelated topics regarding \textit{Cops and Robbers}, a well-known pursuit-evasion game played on a simple graph. First, we address a recent question of Breen et al.~and prove the PSPACE-completeness of the \textit{cop throttling number}, that is, the minimal possible sum of the number $k$ of cops and the number $\operatorname{capt}(k)$ of moves that the robber can survive against $k$ cops under the optimal play of both sides. Secondly, we revisit a \textit{teleporting} version of the game due to Wagner; we disprove one of his conjectures and suggest a new related research problem.

Keywords: Graph theory, cops and robbers

MSC numbers: 05C57, 49N75

Supported by: The author is financially supported by the Russian Science Foundation (project No. 19-71-00063).