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.
Chris Spicer, Department of Mathematical Sciences, Morningside College, Sioux City, Iowa.
Darlington, Elise; Gibbons, Claire; Guy, Kelly; and Hauswald, Jon
"Cops and Robbers on Oriented Graphs,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 17
, Article 14.
Available at: http://scholar.rose-hulman.edu/rhumj/vol17/iss1/14