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.

[img] [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)


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.

Item Type: Thesis (Masters)
Item ID: 15806
Additional Information: Includes bibliographical references (pages 56-57)
Keywords: graphs, cops & robber, combinatorics, geometry, mathematics
Department(s): Science, Faculty of > Mathematics and Statistics
Date: September 2022
Date Type: Submission
Digital Object Identifier (DOI):
Library of Congress Subject Heading: Graph theory; Game theory; Games of strategy (Mathematics); Combinatorial analysis; Geometry

Actions (login required)

View Item View Item


Downloads per month over the past year

View more statistics