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

Rodriguez-Quinche, Juan F. (2022) Cops and robber games on graphs: an approach from large scale geometry. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (1MB)

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.

Actions (login required)

View Item