We consider a variant of Cops and Robbers in which the robber may traverse as many edges as he likes in each turn, with the constraint that he cannot pass through any vertex occupied by a cop. We study this model on several classes of grid-like graphs. In particular, we determine the cop numbers for two-dimensional Cartesian grids and tori up to an additive constant, and we give asymptotic bounds for the cop numbers of higher-dimensional grids and hypercubes.
翻译:我们考虑一个警察和抢劫者的变种, 抢劫者可以绕过他喜欢的边缘, 限制他不能穿过警察占据的任何顶点。 我们用几类网格图形来研究这个模型。 特别是, 我们确定两个维的笛卡尔电网的警察人数, 并给一个添加常数, 我们给高维电网和超立方体的警察人数提供无药可治的界限。