Edge turncoat graphs in the game cops and robbers: the good, the bad and the ugly

Abstract

The game of cops and robbers on a graph is a vertex pursuit game played by two players with perfect information. Per the rules of the game, a given graph is either inherently cop-win or robber-win. It is possible that adding any edge changes the inherent nature of a particular graph. Such a graph is maximal in the sense that no edge can be added without changing its “win-state”. Furthermore, if deleting any edge changes the “win-state”, then this graph is minimal. Join us as we walk this thin blue line between cop-win and robber-win and explore the good, the bad, and the ugly.