The Game of Cops and Robbers on Graphs (Student Mathematical Library, Volume 61)
by Anthony Bonato  (Author), Richard J. Nowakowski (Author)

About the Author
Dr. Anthony Bonato, Full Professor of Mathematics, Ryerson University, Toronto, Canada.
Dr. Richard J. Nowakowski, University Research Professor, Dept. of Mathematics & Statistics, Dalhousie University, Halifax, NS B3H 4R2, Canada.

About this book
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.

Brief contents
Chapter 1. Introduction 1
    §1.1. The Game 1
    §1.2. Interlude on Notation 5
    §1.3. Lower Bounds 10
    §1.4. Upper Bounds 16
    §1.5. Cops, Robbers, and Retracts 20
    Exercises 23
Chapter 2. Characterizations 29
    §2.1. Introduction 29
    §2.2. Characterizing Cop-win Graphs 30
    §2.3. Characterizing Graphs with Higher Cop Number 39
    Exercises 48
Chapter 3. Meyniel’s Conjecture 53
    §3.1. Introduction 53
    §3.2. An Improved Upper Bound for the Cop Number 56
    §3.3. How Close to
    §3.4. Meyniel’s Conjecture in Graph Classes 66
    Exercises 73
Chapter 4. Graph Products and Classes 79
    §4.1. Introduction 79
    §4.2. Cop Numbers and Corners in Products 83
    §4.3. Covering by Cop-win Graphs 86
    §4.4. Genus of a Graph 92
    §4.5. Outerplanar Graphs 95
    §4.6. Planar Graphs 98
    Exercises 105
Chapter 5. Algorithms 109
    §5.1. Introduction 109
    §5.2. Background on Complexity 112
    §5.3. Polynomial Time with k Fixed 119
    §5.4. NP-hard with k Not Fixed 124
    §5.5. Open Problems 127
    Exercises 128
Chapter 6. Random Graphs 133
    §6.1. Introduction 133
    §6.2. Constant p and log n Many Cops 136
    §6.3. Variable p and Bounds 139
    §6.4. The Zig-Zag Theorem 149
    §6.5. Cops and Robbers in the Web Graph 153
    Exercises 162
Chapter 7. Infinite Graphs 165
    §7.1. Introduction 165
    §7.2. Introducing the Infinite Random Graph 167
    §7.3. Cop Density 172
    §7.4. Infinite Chordal Graphs 178
    §7.5. Vertex-transitive Cop-win Graphs 182
    Exercises 187
Chapter 8. Variants of Cops and Robbers 191
    §8.1. Imperfect Information 192
    §8.2. Traps 199
    §8.3. Tandem-win 203
    §8.4. Playing on Different Edge Sets 205
    §8.5. Distance k Cops and Robbers 209
    §8.6. Capture Time 215
    Exercises 219
Chapter 9. Good Guys Versus Bad Guys 221
    §9.1. Introduction 221
    §9.2. Firefighter 223
    §9.3. Seepage 230
    §9.4. Graph Searching 233
    §9.5. Helicopter Cops and Robbers and Marshals 237
    §9.6. Cleaning 239
    §9.7. Combinatorial Games 252
    Exercises 256
Bibliography 259
Index 273

Series: Student Mathematical Library (Book 61)
Pages: 276 pages
Publisher: American Mathematical Society (September 2, 2011)
Language: English
ISBN-10: 0821853473
ISBN-13: 978-0821853474