Series:

Student Mathematical Library

2 total works

Cover of The Game of Cops and Robbers on Graphs
This book is the first and only one of its kind on the topic of Cops and Robbers games, and more generally, on the field of vertex pursuit games on graphs. The book is written in a lively and highly readable fashion, which should appeal to both senior undergraduates and experts in the field (and everyone in between). One of the main goals of the book is to bring together the key results in the field; as such, it presents structural, probabilistic, and algorithmic results on Cops and Robbers games. Several recent and new results are discussed, along with a comprehensive set of references. The book is suitable for self-study or as a textbook, owing in part to the over 200 exercises. The reader will gain insight into all the main directions of research in the field and will be exposed to a number of open problems.

Cover of An Invitation to Pursuit-Evasion Games and Graph Theory
Graphs measure interactions between objects such as friendship links on Twitter, transactions between Bitcoin users, and the flow of energy in a food chain. While graphs statically represent interacting systems, they may also be used to model dynamic interactions. For example, imagine an invisible evader loose on a graph, leaving behind only breadcrumb clues to their whereabouts. You set out with pursuers of your own, seeking out the evader's location. Would you be able to detect their location? If so, then how many resources are needed for detection, and how fast can that happen? These basic-seeming questions point towards the broad conceptual framework of pursuit-evasion games played on graphs. Central to pursuit-evasion games on graphs is the idea of optimizing certain parameters, whether they are the cop number, burning number, or localization number, for example.

This book would be excellent for a second course in graph theory at the undergraduate or graduate level. It surveys different areas in graph searching and highlights many fascinating topics intersecting classical graph theory, geometry, and combinatorial designs. Each chapter ends with approximately twenty exercises and five larger scale projects.