Two remarks on the game of Cops and Robbers
Bull. Korean Math. Soc.
Published online December 17, 2019
Yaroslav Shitov
Moscow Institute of Physics and Technology
Abstract : We discuss two unrelated topics regarding 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 cop throttling number, that is, the minimal possible sum of the number k of cops and the number capt(k) of moves that the robber can survive against k cops under the optimal play of both sides. Secondly, we revisit a 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
Full-Text :

   

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