The Game of Cops and Robbers in Graphs

Publisher:
American Mathematical Society
Number of Pages:
276
Price:
45.00
ISBN:
9780821853474

As the title suggests, The Game of Cops and Robbers on Graphs is a book about a game that you play on graphs. In the basic version of the game there is a single robber that is on one vertex of the graph and a collection of cops on other vertices of the graph. The cops and robbers take turns moving, and on a given turn they can move to any adjacent vertex. Can the robber stay alive forever, outrunning all of the cops, or can the cops corner the robber eventually?

A little thought will convince you that it depends on the graph, on the number of cops, and on the starting positions of the various players, which means that the question leads to some interesting mathematics. A typical question is to fix a connected graph with n vertices, allow the cops to choose their starting positions, and ask whether there is any place that the robber can choose to start so that he will be able to outrun the cops. Clearly if there are n–1 cops then the answer is no — the robber must start in a place connected to cops at all edges and therefore he is dead in the water. It is also clear that if there are no cops then the robber is home free.

So one natural question to ask is what is the minimum number of cops so that wherever they start the robber can evade capture — this number is defined to be the cop number of a graph. It turns out that it is not too complicated to classify those graphs for which a robber can always evade a single cop, but with more than one cop the strategies become increasingly complicated, and calculating this number turns out to be an interesting problem. As the authors write, “all robust fields of mathematics need at least one easy to state but tough to solve problem.” Meyniel’s conjecture, stating that the cop number of a graph is on the order of the square root of the number of vertices, is their example for this field.

Bonato and Nowakaski discuss the question in general and also analyze what happens in special cases — what if the graph is a product of other graphs? What if the graph has an infinite number of vertices? What can one say about the theory as it applies to random graphs? What types of algorithms can one develop to calculate the cop number in specific cases, and what is the complexity of these algorithms? What happens if you consider other variations, where maybe the cops have only partial information about the location of the robber, or the different players move at different speeds? The authors draw you in to these questions giving many concrete examples and exercises to play with. Throughout the book, they do a nice job of explaining what is known and also what is unknown, keeping the reader abreast of developments in the theory as recent as last year.

The authors do a wonderful job of keeping the exposition lively and engaging, while still covering some deep mathematics and introducing some fascinating ideas. The technical background required to read the book is relatively low, and the authors do a good job of introducing the relevant background as needed. For these reasons, as well as the fact that the subject is itself engaging, this is a book that I would happily hand to an undergraduate math major for an independent study, capstone project, or even just to read for fun! But it is also a book that I think any mathematician could pick up and quickly learn something new and interesting. And I cannot think of a higher compliment to give than that.

Darren Glass is an Associate Professor of Mathematics at Gettysburg College. He can be reached at dglass@gettysburg.edu.

Friday, August 19, 2011
Reviewable:
Yes
Include In BLL Rating:
Yes
Anthony Bonato and Richard J. Nowakowski
Series:
Student Mathematical Library 61
Publication Date:
2011
Format:
Paperback
Category:
Monograph
Darren Glass
12/29/2011
BLL Rating:
• Introduction
• Characterizations
• Meyniel's conjecture
• Graph products and classes
• Algorithms
• Random graphs
• Infinite graphs
• Variants of Cops and Robbers
• Good guys versus bad guys
• Bibliography
• Index
Publish Book:
Modify Date:
Thursday, May 31, 2012