Cops and Robber on some families of oriented graphs

2021 
is a two-player pursuit-evasion game in which a set of , controlled by Player 1, try to capture the , controlled by Player 2. We study three models of this game on oriented graphs which differ based on the kind of moves the players can make. These models are (i) the , where both cops and robber can only move along the direction of the arcs; (ii) the , where the cops can move along or against the direction of the arcs while the robber can only move along them; and (iii) the , where the robber can move along or against the direction of the arcs while the cops can only move along them. The is the minimum number of cops required to capture the robber in a graph, and a graph is if its cop number is 1.We begin our study by comparing the cop number in these three models for oriented graphs. For the normal cop model, we show that there exist strongly connected oriented graphs having high girth, high minimum degree, and high cop number. We also characterize the cop-win graphs in various graph classes like transitive-triangle-free, outerplanar, and subcubic graphs. For the strong cop model, we construct graphs with unbounded cop number, and also study the cop number of grids, outerplanar, and planar graphs. For the weak cop model, we characterize the cop-win graphs.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    0
    References
    0
    Citations
    NaN
    KQI
    []