ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2019: 0.600
Rejection Rate (2018-2019): c. 84%
Article in press
D. Offner, K. Ojakian
Capture-time extremal cop-win graphs
Discussiones Mathematicae Graph Theory
We investigate extremal graphs related to the game of Cops and Robbers.
We focus on graphs where a single cop can catch the robber; such graphs are
called cop-win. The capture time of a cop-win graph is the minimum number of
moves the cop needs to capture the robber. We consider graphs that are extremal
with respect to capture time, i.e., their capture time is as large as possible
given their order. We give a new characterization of the set of extremal graphs.
For our alternative approach we assign a rank to each vertex of a graph, and
then study which configurations of ranks are possible. We partially determine
which configurations are possible, enough to prove some further extremal results.
We leave a full classification as an open question.
pursuit-evasion games, cops and robbers, cop-win graphs,
capture time, extremal graphs