Cops and Robber is a family of two-player games played on graphs in which one player controls a number of cops and the other player controls a robber. In alternating turns, each player moves (all) his/her figures. The cops try to capture the robber while the latter tries to flee indefinitely. In this paper we consider a variant of the game played on a planar graph where the robber moves between adjacent vertices while the cops move between adjacent faces. The cops capture the robber if they occupy all incident faces. We prove that a constant number of cops suffices to capture the robber on any planar graph of maximum degree $\Delta$ if and only if $\Delta \leq 4$.
翻译:警察和强盗是一个由两个玩家组成的家族, 玩家在图表上玩两个游戏, 其中一个玩家控制着几个警察, 另一个玩家控制着一个强盗。 在交替轮转中, 每个玩家移动( 全部) 他/ 她的数字。 警察试图抓住强盗, 而后者却试图无限期逃跑。 在本文中, 我们考虑一个游戏的变种, 在平板图上, 强盗移动在邻近的悬崖之间, 而警察移动在相邻的面孔之间。 警察抓捕强盗, 如果他们占领了所有事件的脸。 我们证明, 经常有警察来抓强盗, 只要能用最高水平的平板图 $\ Delta$, 并且只有$\ Delta\leq 4$, 并且只有$\ Delta\leq 4$ 。