Carnegie Mellon University
Browse

Cops and robbers on planar directed graphs

Download (495.42 kB)
journal contribution
posted on 2015-07-01, 00:00 authored by Po-Shen Loh, Siyoung Oh

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 which shows that a more sophisticated robber strategy can indefinitely evade three cops on a particular strongly connected planar directed graph

History

Date

2015-07-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC