Catching an infinitely fast robber on a grid. (English) Zbl 1495.05190
Summary: We consider a variant of Cops and Robbers in which the robber may traverse as many edges as he likes in each turn, with the constraint that he cannot pass through any vertex occupied by a cop. We study this model on several classes of grid-like graphs. In particular, we determine the cop numbers for two-dimensional Cartesian grids and tori up to an additive constant, and we give asymptotic bounds for the cop numbers of higher-dimensional grids and hypercubes.
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 91A43 | Games involving graphs |
| 91A24 | Positional games (pursuit and evasion, etc.) |
References:
| [1] | Aigner, M.; Fromme, M., A game of cops and robbers, Discrete Appl. Math., 8, 1-12 (1984) · Zbl 0539.05052 |
| [2] | Alon, N.; Mehrabian, A., On a generalization of Meyniel’s conjecture on the cops and Robbers game, Electron. J. Combin., 18, 1, 7 (2011), Paper 19 · Zbl 1205.05159 |
| [3] | Alon, N.; Mehrabian, A., Chasing a fast robber on planar graphs and random graphs, J. Graph Theory, 78, 2, 81-96 (2015) · Zbl 1305.05142 |
| [4] | Bal, D.; Bonato, A.; Kinnersley, W. B.; Prałat, P., Lazy cops and robbers on hypercubes, Combin. Probab. Comput., 24, 829-837 (2015) · Zbl 1371.05178 |
| [5] | Balister, P.; Bollobás, B.; Narayanan, B. P.; Shaw, A., Catching a fast robber on the grid, J. Combin. Theory Ser. A, 152, 341-352 (2017) · Zbl 1369.05145 |
| [6] | Bollobás, B.; Leader, I., Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A, 56, 47-62 (1991) · Zbl 0731.05043 |
| [7] | Bonato, A.; Nowakowski, R. J., The Game of Cops and Robbers on Graphs (2011), American Mathematical Society: American Mathematical Society Providence, Rhode Island · Zbl 1298.91004 |
| [8] | Dereniowski, D.; Gavenčiak, T.; Kratochvíl, J., Cops, a fast robber and defensive domination on interval graphs, Theor. Comp. Sci., 794, 47-58 (2019) · Zbl 1433.91033 |
| [9] | Fomin, F.; Golovach, P.; Kratochvíl, J.; Nisse, N.; Suchan, K., Pursuing a fast robber on a graph, Theor. Comp. Sci., 411, 1167-1181 (2010) · Zbl 1192.91027 |
| [10] | Frieze, A.; Krivilevich, M.; Loh, P., Variations on cops and robbers, J. Graph Theory, 69, 4, 383-402 (2012) · Zbl 1243.05165 |
| [11] | Harper, L., Optimal numberings and isoperimetric problems on graphs, J. Comb. Theory, 1, 3, 385-393 (1966) · Zbl 0158.20802 |
| [12] | Hickingbotham, R.; Wood, D. R., Structural properties of graph products (2021), arXiv:2110.00721 |
| [13] | Maamoun, M.; Meyniel, H., On a game of policemen and robber, Discrete Appl. Math., 17, 307-309 (1987) · Zbl 0615.05049 |
| [14] | Mehrabian, A., Cops and robber game with a fast robber on expander graphs and random graphs, Ann. Comb., 16, 4, 829-846 (2012) · Zbl 1256.05151 |
| [15] | Mehrabian, A., The fast robber on interval and chordal graphs, Discrete Appl. Math., 180, 188-193 (2015) · Zbl 1303.05128 |
| [16] | Nowakowski, R. J.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235-239 (1983) · Zbl 0508.05058 |
| [17] | Okamoto, M., Some inequalities relating to the partial sum of binomial probabilities, Ann. Inst. Stat. Math., 10, 29-35 (1959) · Zbl 0084.14001 |
| [18] | Otachi, Y.; Suda, R., Bandwidth and pathwidth of three-dimensional grids, Discrete Math., 311, 10-11, 881-887 (2011) · Zbl 1223.05142 |
| [19] | Quilliot, A., Jeux Et Pointes Fixes sur Les Graphes, Thèse de 3ème Cycle, 131-145 (1978), Univerité de Paris VI |
| [20] | Spencer, J.; Florescu, L., Asymptopia, Student Mathematical Library. Vol. 71 (2014), AMS: AMS Providence, RI · Zbl 1331.00002 |
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.
