Cops and robber – when capturing is not surrounding. (English) Zbl 07842227
Paulusma, Daniël (ed.) et al., Graph-theoretic concepts in computer science. 49th international workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 14093, 403-416 (2023).
Summary: We consider “surrounding” versions of the classic Cops and Robber game. The game is played on a connected graph in which two players, one controlling a number of cops and the other controlling a robber, take alternating turns. In a turn, each player may move each of their pieces. The robber always moves between adjacent vertices. Regarding the moves of the cops we distinguish four versions that differ in whether the cops are on the vertices or the edges of the graph and whether the robber may move on/through them. The goal of the cops is to surround the robber, i.e., occupying all neighbors (vertex version) or incident edges (edge version) of the robber’s current vertex. In contrast, the robber tries to avoid being surrounded indefinitely. Given a graph, the so-called cop number denotes the minimum number of cops required to eventually surround the robber.
We relate the different cop numbers of these versions and prove that none of them is bounded by a function of the classical cop number and the maximum degree of the graph, thereby refuting a conjecture by Crytser, Komarov and Mackey [Graphs and Combinatorics, 2020].
For the entire collection see [Zbl 1535.68010].
We relate the different cop numbers of these versions and prove that none of them is bounded by a function of the classical cop number and the maximum degree of the graph, thereby refuting a conjecture by Crytser, Komarov and Mackey [Graphs and Combinatorics, 2020].
For the entire collection see [Zbl 1535.68010].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Aigner, MS; Fromme, M., A game of cops and robbers, Discret. Appl. Math., 8, 1, 1-12 (1984) · Zbl 0539.05052 · doi:10.1016/0166-218X(84)90073-8 |
| [2] | Baird, W., Bonato, A.: Meyniel’s conjecture on the cop number: a survey (2013). https://arxiv.org/abs/1308.3385 · Zbl 1276.05074 |
| [3] | Bonato, A., An Invitation to Pursuit-Evasion Games and Graph Theory (2022), Providence: American Mathematical Society, Providence · Zbl 1500.91001 · doi:10.1090/stml/097 |
| [4] | Bonato, A., Nowakowski, R.J.: The Game of Cops and Robbers on Graphs. American Mathematical Society, Providence (2011). doi:10.1090/stml/061 · Zbl 1298.91004 |
| [5] | Bradshaw, P., Hosseini, S.A.: Surrounding cops and robbers on graphs of bounded genus (2019). https://arxiv.org/abs/1909.09916 |
| [6] | Burgess, AC, Cops that surround a robber, Discret. Appl. Math., 285, 552-566 (2020) · Zbl 1447.05132 · doi:10.1016/j.dam.2020.06.019 |
| [7] | Crytser, D.; Komarov, N.; Mackey, J., Containment: a variation of cops and robbers, Graphs Comb., 36, 3, 591-605 (2020) · Zbl 1439.05152 · doi:10.1007/s00373-020-02140-5 |
| [8] | Frankl, P., Cops and robbers in graphs with large girth and Cayley graphs, Discret. Appl. Math., 17, 3, 301-305 (1987) · Zbl 0624.05041 · doi:10.1016/0166-218X(87)90033-3 |
| [9] | Ha, M.T., Jungeblut, P., Ueckerdt, T.: Primal-dual cops and robber. In: Seara, C., Huemer, C. (eds.) Proceedings of the 39th European Workshop on Computational Geometry (EuroCG) (2023). https://arxiv.org/abs/2301.05514 |
| [10] | Jungeblut, P., Schneider, S., Ueckerdt, T.: Cops and Robber - When Capturing is not Surrounding (2023). doi:10.48550/arXiv.2302.10577 |
| [11] | Keedwell, D.A., Dénes, J.: Latin Squares and their Applications. 2nd edn. Elsevier, Amsterdam (2015). doi:10.1016/C2014-0-03412-0 · Zbl 1318.05001 |
| [12] | Kinnersley, WB, Cops and Robbers is EXPTIME-complete, J. Comb. Theory Ser. B, 111, 201-220 (2015) · Zbl 1307.05155 · doi:10.1016/j.jctb.2014.11.002 |
| [13] | Nowakowski, RJ; Winkler, P., Vertex-to-vertex pursuit in a graph, Discret. Math., 43, 2-3, 235-239 (1983) · Zbl 0508.05058 · doi:10.1016/0012-365X(83)90160-7 |
| [14] | Prałat, P.: Containment game played on random graphs: another zig-zag theorem. Electron. J. Comb. 22(2) (2015). doi:10.37236/4777 · Zbl 1328.05122 |
| [15] | Quilliot, A.: Jeux et pointes fixes sur les graphes. Ph.D. thesis, Université de Paris VI (1978) |
| [16] | Schneider, S.: Surrounding cops and robbers. Bachelor’s thesis, Karlsruhe Institute of Technology (2022). https://i11www.iti.kit.edu/_media/teaching/theses/ba_schneider22.pdf |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
