×

zbMATH — the first resource for mathematics

Fully active cops and robbers. (English) Zbl 1439.05154
Summary: We study a variation of the classical pursuit-evasion game of Cops and Robbers in which agents are required to move to an adjacent vertex on every turn. We explore how the minimum number of cops needed to catch the robber can change when this condition is added to the rules of the game. We study this “fully active Cops and Robbers” game for a number of classes of graphs and present some open problems for future research.
MSC:
05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
91A24 Positional games (pursuit and evasion, etc.)
PDF BibTeX XML Cite
Full Text: Link
References:
[1] M. Aigner and M. Fromme, A game of cops and robbers,Discrete Appl. Math. 8 (1) (1984), 1-12. · Zbl 0539.05052
[2] D. Bal, A. Bonato, W. B. Kinnersley and P. Pralat, Lazy cops and robbers on hypercubes,Combin. Probab. Comput.24 (6) (2015), 829-837. · Zbl 1371.05178
[3] D. Bal, A. Bonato, W. B. Kinnersley and P. Pralat, Lazy cops and robbers played on random graphs and graphs on surfaces,J. Comb.7 (2016), 627-642. · Zbl 1350.05102
[4] A. Bonato and R. Nowakowski, The game of cops and robbers on graphs,Student Math. Library61, American Mathematical Society, Providence, RI, 2011. · Zbl 1298.91004
[5] G. R. Brightwell and P. Winkler, Gibbs Measures and Dismantlable Graphs, J. Combin. Theory Ser. B78 (1) (2000), 141-166. · Zbl 1030.05101
[6] N. E. Clarke, Constrained Cops and Robber,PhD Thesis, Dalhousie University, 2002.
[7] Z. Gao and B. Yang, The cop number of the one-cop-moves game on planar graphs,Combinatorial optimization and applications (Part II), 199-213, Lec. Notes in Comp. Sci. 10628, Springer, Cham, 2017. · Zbl 06852645
[8] M. Maamoun and H. Meyniel, On a game of policemen and robber,Discrete Appl. Math.17 (3) (1987), 307-309. · Zbl 0615.05049
[9] S. Neufeld and R. Nowakowski, A game of cops and robbers played on products of graphs,Discrete Math.186 (1-3) (1998), 253-268. · Zbl 0957.91029
[10] R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph,Discrete Math.43 (2) (1983), 235-239. · Zbl 0508.05058
[11] D. Offner and K. Ojakian, Variations of Cops and Robber on the hypercube, Australas. J. Combin.59 (2) (2014), 229-250. · Zbl 1296.05130
[12] A. Quilliot, Jeux et Points Fixes sur les graphes,Th‘ese de 3‘eme cycle, Universit´e de Paris VI, 1978.
[13] A. Quilliot, Probl‘emes de jeux, de point fixe, de connectivit´e et d representation sur des graphes, des ensembles ordonn´es et des hypergraphe.Th‘ese d’Etat, Universit´e de Paris VI, 1983.
[14] B. S. Schr¨oder, The copnumber for lexicographic products and sums of graphs, Contrib. Discrete Math.9 (2) (2014), 45-49.
[15] B.
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.