Start Date
April 2025
Location
MCD 130
Abstract
Cops and Robbers is a two-player vertex-to-vertex pursuit game played on a reflexive graph. The goal is for the cop(s) to occupy the same vertex as the robber. The game is played with exactly one robber and at least one cop. If k is the least number of cops needed to always capture the robber on a graph G, then G has cop number k and we say G is k-cop-win. The game has been well studied for undirected graphs. We investigate oriented graphs where each edge (or arc) has exactly one of the two possible orientations. There is no known intrinsic characterization of 1-cop-win oriented graphs. In this presentation, we define a relational characterization of the class of cop-win oriented graphs in a manner analogous to the characterization provided by Clarke and McGillivray (2012) for undirected graphs. We will also discuss the cop number of products of oriented graphs, with a focus on oriented cycles.
Cops and Robbers on Oriented Graphs
MCD 130
Cops and Robbers is a two-player vertex-to-vertex pursuit game played on a reflexive graph. The goal is for the cop(s) to occupy the same vertex as the robber. The game is played with exactly one robber and at least one cop. If k is the least number of cops needed to always capture the robber on a graph G, then G has cop number k and we say G is k-cop-win. The game has been well studied for undirected graphs. We investigate oriented graphs where each edge (or arc) has exactly one of the two possible orientations. There is no known intrinsic characterization of 1-cop-win oriented graphs. In this presentation, we define a relational characterization of the class of cop-win oriented graphs in a manner analogous to the characterization provided by Clarke and McGillivray (2012) for undirected graphs. We will also discuss the cop number of products of oriented graphs, with a focus on oriented cycles.
