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.
Darlington, Elise; Gibbons, Claire; Guy, Kelly; and Hauswald, Jon
"Cops and Robbers on Oriented Graphs,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 17:
1, Article 14.
Available at: https://scholar.rose-hulman.edu/rhumj/vol17/iss1/14