Two remarks on the game of Cops and Robbers
Bull. Korean Math. Soc. 2020 Vol. 57, No. 1, 127-131
https://doi.org/10.4134/BKMS.b190097
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: paper@kms.or.kr   | Powered by INFOrang Co., Ltd