Cops and Robbers on Planar‐Directed Graphs. Issue 3 (21st April 2017)

• Record Type: Journal Article
• Authors: Loh, Po‐Shen; Oh, Siyoung
• Is Part Of: Journal of graph theory. Volume 86:Issue 3(2017)
• Page Start: 329
• Page End: 340
• Publication Date: 2017-04-21
• Subjects: cops and robbers -- planar graph -- digraph -- pursuit game; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22129
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Aigner and Fromme initiated the systematic study of the cop number of a graph by proving the elegant and sharp result that in every connected planar graph, three cops are sufficient to win a natural pursuit game against a single robber. This game, introduced by Nowakowski and Winkler, is commonly known as Cops and Robbers in the combinatorial literature. We extend this study to directed planar graphs, and establish separation from the undirected setting. We exhibit a geometric construction that shows that a sophisticated robber strategy can indefinitely evade three cops on a particular strongly connected planar‐directed graph.