Two remarks on the game of Cops and Robbers
Bull. Korean Math. Soc. 2020 Vol. 57, No. 1, 127-131
Published online January 31, 2020
Yaroslav Shitov
Moscow Institute of Physics and Technology
Abstract : 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
Downloads: Full-text PDF   Full-text HTML


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail:   | Powered by INFOrang Co., Ltd