Cops and Robbers on Planar‐Directed Graphs |
| |
| Authors: | Po‐Shen Loh Siyoung Oh |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICAL SCIENCES, CARNEGIE MELLON UNIVERSITY, PITTSBURGHContract grant sponsor: NSA Young Investigators Grant, contract grant sponsor: NSF;2. contract grant numbers: DMS‐1201380 and DMS‐1455125;3. contract grant sponsor: USA‐Israel BSF Grant.;4. GOOGLE INC., MOUNTAIN VIEWResearch conducted for Masters Thesis at Carnegie Mellon University. |
| |
| 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. |
| |
| Keywords: | cops and robbers planar graph digraph pursuit game |
|
|
