Cops and Robbers on Oriented Graphs
Elise Darlington, C. H. Gibbons, Kelly Guy, Jon Hauswald · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · 2016
Cops and Robbers is a turn-based game traditionally played on graphs. Similar to the classic children's game, one cop and one robber move along edges in a graph with the cop trying to catch the robber, and the robber trying to evade capture. In this article, we extend this game to oriented graphs. Although a complete characterization of 1-cop-win graphs is known, there is not yet a corresponding characterization for oriented graphs. Necessary conditions are described for an oriented graph to be 1-cop-win, and several results are provided toward finding sufficient conditions.