A cops and robber game in multidimensional grids

作者：Bhattacharya Sayan; Paul Goutam^*; Sanyal Swagato

来源：Discrete Applied Mathematics, 2010, 158(16): 1745-1751.

DOI：10.1016/j.dam.2010.06.014

• Cops and robber
• Game
• Graph
• Grid
• Winning strategy

We theoretically analyze the 'cops and robber' game for the first time in a multidimensional grid. It is shown that in an n-dimensional grid, at least n cops are necessary if one wants to catch the robber for all possible initial configurations. We also present a set of cop strategies for which n cops are provably sufficient to catch the robber. Further, we revisit the game in a two-dimensional grid and provide an independent proof of the fact that the robber can be caught even by a single cop under certain conditions.

• 出版日期2010-8-28