zbMATH — the first resource for mathematics

The game of overprescribed Cops and Robbers played on graphs. (English) Zbl 1371.05179
Summary: We consider the effect on the length of the game of Cops and Robbers when more cops are added to the game play. In Overprescribed Cops and Robbers, as more cops are added, the capture time (the minimum length of the game assuming optimal play) monotonically decreases. We give the full range of capture times for any number of cops on trees, and classify the capture time for an asymptotic number of cops on grids, hypercubes, and binomial random graphs. The capture time of planar graphs with a number of cops at and far above the cop number is considered.

05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
91A24 Positional games (pursuit and evasion, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Aigner, M; Fromme, M, A game of cops and robbers, Discret. Appl. Math., 8, 1-11, (1984) · Zbl 0539.05052
[2] Alon, N; Seymour, P; Thomas, R, Planar separators, SIAM J. Discret. Math., 7, 184-193, (1994) · Zbl 0797.05039
[3] Berarducci, A; Intriglia, B, On the cop number of a graph, Adv. Appl. Math., 14, 389-403, (1993) · Zbl 0801.90150
[4] Bollobás, B; Kun, G; Leader, I, Cops and robbers in a random graph, J. Combin. Theory Series B, 103, 226-236, (2013) · Zbl 1261.05064
[5] Bonato, A; Golovach, P; Hahn, G; Kratochvíl, J, The capture time of a graph, Discret. Math., 309, 5588-5595, (2009) · Zbl 1177.91056
[6] Bonato, A., Gordinowicz, P., Kinnersley, W.B., Prałat, P.: The capture time of the hypercube. Electron. J. Combin. 20(2), P24 (2013) · Zbl 1266.05096
[7] Bonato, A., MacGillivray, G.: Characterizations and algorithms for generalized Cops and Robbers games (2017) (Preprint) · Zbl 1376.05087
[8] Bonato, A., Nowakowski, R.: The Game of Cops and Robbers on Graphs. American Mathematical Society, Rhode Island (2011) · Zbl 1298.91004
[9] Bonato, A; Prałat, P; Wang, C, Network security in models of complex networks, Int. Math., 4, 419-436, (2009) · Zbl 1206.68030
[10] Gavenčiak, T, Cop-win graphs with maximum capture-time, Discret. Math., 310, 1557-1563, (2010) · Zbl 1186.91051
[11] Gilbert, JR; Hutchinson, JP; Tarjan, RE, A separator theorem for graphs of bounded genus, J. Algorithm, 5, 391-407, (1984) · Zbl 0556.05022
[12] Janson, S., Łuczak, T., Ruciński, A.: Random Graphs. Wiley, New York (2000) · Zbl 0968.05003
[13] Łuczak, T; Prałat, P, Chasing robbers on random graphs: zigzag theorem, Random Struct. Algorithms, 37, 516-524, (2010) · Zbl 1209.05226
[14] Maamoun, M; Meyniel, H, On a game of policemen and robber, Discret. Appl. Math., 17, 307-309, (1987) · Zbl 0615.05049
[15] Mehrabian, A, The capture time of grids, Discret. Math., 311, 102-105, (2011) · Zbl 1203.91039
[16] Nowakowski, RJ; Winkler, P, Vertex-to-vertex pursuit in a graph, Discret. Math., 43, 235-239, (1983) · Zbl 0508.05058
[17] Quilliot, A.: Jeux et pointes fixes sur les graphes, Thèse de 3ème cycle, Université de Paris VI, 131-145 (1978) · Zbl 0797.05039
[18] Panconesi, A; Srinivasan, A, Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds, SIAM J. Comput., 26, 350-368, (1997) · Zbl 0867.05063
[19] Prałat, P., Wormald, N.: Meyniel’s conjecture holds for random d-regular graphs, Preprint (2017) · Zbl 1332.05096
[20] Prałat, P; Wormald, N, Meyniel’s conjecture holds for random graphs, Random Struct. Algorithm., 48, 396-421, (2016) · Zbl 1332.05096
[21] Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2003)
[22] West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, New Jersey (2001)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.