Geodesic
Capture-Time Extremal Cop-Win Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 923-948.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: pursuit-evasion games, cops and robbers, cop-win graphs, capture time, extremal graphs 
@article{DMGT_2021_41_4_a4,
     author = {Offner, David and Ojakian, Kerry},
     title = {Capture-Time {Extremal} {Cop-Win} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {923--948},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a4/}
}
TY  - JOUR
AU  - Offner, David
AU  - Ojakian, Kerry
TI  - Capture-Time Extremal Cop-Win Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 923
EP  - 948
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a4/
LA  - en
ID  - DMGT_2021_41_4_a4
ER  - 
%0 Journal Article
%A Offner, David
%A Ojakian, Kerry
%T Capture-Time Extremal Cop-Win Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 923-948
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a4/
%G en
%F DMGT_2021_41_4_a4
Offner, David; Ojakian, Kerry. Capture-Time Extremal Cop-Win Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 923-948. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a4/

[1] A. Bonato and R. Nowakowski, The Game of Cops and Robbers on Graphs (AMS Student Mathematical Library, 2011).

[2] A. Bonato, P. Golovach G. Hahn and J. Kratochvil, The capture time of a graph, Discrete Math. 309 (2009) 5588–5595. https://doi.org/10.1016/j.disc.2008.04.004

[3] N. Clarke, S. Finbow and G. MacGillivray, A simple method of computing the catch time, Ars Math. Contemp. 7 (2014) 353–359. https://doi.org/10.26493/1855-3974.304.fec

[4] T. Gavenciak, Cop-win graphs with maximum capture-time, Discrete Math. 310 (2010) 1557–1563. https://doi.org/10.1016/j.disc.2010.01.015

[5] W. Kinnersley, Bounds on the length of a game of Cops and Robbers, Discrete Math. 341 (2018) 2508–2518. https://doi.org/10.1016/j.disc.2018.05.025

[6] R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43 (1983) 235–239. https://doi.org/10.1016/0012-365X(83)90160-7

[7] D. Offner and K. Ojakian, Cop-win graphs: Optimal strategies and corner rank (2017). arXiv: org/abs/1607.03471

[8] D. Offner and K. Ojakian, Graphical examples of cop-win graphs . arXiv: org/abs/1703.04427

[9] A. Quilliot, Jeux et Pointes Fixes sur les Graphes (Ph.D. Dissertation, Université de Paris VI, 1978).