zbMATH — the first resource for mathematics

The game of cops and robbers on graphs. (English) Zbl 1298.91004
Student Mathematical Library 61. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-5347-4/pbk). xix, 276 p. (2011).
This is a textbook that presents the state of the art in the literature on cops and robber games and, more generally, vertex pursuit games on graphs. The cops and robber game was first introduced in the 1980s and there has been a growing literature on this topic. It is a two-player, zero-sum game where one player controls a set of cops and the other player controls the robber. The first player’s objective is to capture the robber. The game is played on a graph, cops and robber are restricted to vertices and they move each round to neighboring vertices. The book, which is written in a lively and highly readable fashion, is suitable for both advanced undergraduate and beginner graduate students, but it also covers advanced topics that will be of interest to researchers in mathematics, computer science and game theory. There are over 200 exercises in the book, with many worked out examples. Many open problems are listed throughout the book and a comprehensive set of references is provided.

91-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to game theory, economics, and finance
91A43 Games involving graphs
91A05 2-person games
91A24 Positional games (pursuit and evasion, etc.)
05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05C75 Structural characterization of families of graphs
05C57 Games on graphs (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
05C63 Infinite graphs
05C80 Random graphs (graph-theoretic aspects)