Cops and robber games on graphs: an approach from large scale geometry

Abstract

We introduce two variations of the cops and robber game for graphs which define two invariants for infinite connected graphs: the weak-cop number and the strong-cop number. We exhibit examples of graphs with arbitrary weak-cop number, and examples with arbitrary strong-cop number. We prove that these invariants are preserved by quasi-isometry; for example, this allow us to show that the square-grid, triangulargrid and hexagonal-grid have the same weak-cop number and the same strong-cop number. We also prove that hyperbolic graphs have strong cop number one; for example this implies that any graph arising as a regular tiling of the hyperbolic plane has strong cop-number one. Our main result is that one-ended non-amenable locally- finite vertex-transitive graphs have infinite weak-cop number. This last result includes graphs arising as regular tilings of the hyperbolic plane.