A tandem version of the cops and robber game played on products of graphs
Nancy E. Clarke ; Richard J. Nowakowski
Discussiones Mathematicae Graph Theory, Tome 25 (2005), p. 241-249 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this version of the Cops and Robber game, the cops move in tandems, or pairs, such that they are at distance at most one from each other after every move. The problem is to determine, for a given graph G, the minimum number of tandems sufficient to guarantee a win for the cops. We investigate this game on three graph products, the Cartesian, categorical and strong products.

Publié le : 2005-01-01
EUDML-ID : urn:eudml:doc:270333 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1277,
     author = {Nancy E. Clarke and Richard J. Nowakowski},
     title = {A tandem version of the cops and robber game played on products of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {25},
     year = {2005},
     pages = {241-249},
     zbl = {1148.91009},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1277}
}

Nancy E. Clarke; Richard J. Nowakowski. A tandem version of the cops and robber game played on products of graphs. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 241-249. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1277/

[000] [1] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph classes: a survey, SIAM Monographs on Discrete Math. and Appl., Society for Industrial and Applied Mathematics (SIAM) (Philadelphia, PA, 1999). | Zbl 0919.05001

[001] [2] N.E. Clarke, Constrained Cops and Robber (Ph.D. Thesis, Dalhousie University, 2002).

[002] [3] N.E. Clarke and R.J. Nowakowski, Tandem-win Graphs, to appear in Discrete Math. | Zbl 1073.05060

[003] [4] W. Imrich and H. Izbicki, Associative Products of Graphs, Monatshefte für Mathematik 80 (1975) 277-281, doi: 10.1007/BF01472575. | Zbl 0328.05136

[004] [5] M. Maamoun and H. Meyniel, On a game of policeman and robber, Discrete Appl. Math. 17 (1987) 307-309, doi: 10.1016/0166-218X(87)90034-5. | Zbl 0615.05049

[005] [6] S. Neufeld and R.J. Nowakowski, A Game of Cops and Robbers Played on Products of Graphs, Discrete Math. 186 (1998) 253-268, doi: 10.1016/S0012-365X(97)00165-9. | Zbl 0957.91029

[006] [7] R.J. Nowakowski and P. Winkler, Vertex to vertex pursuit in a graph, Discrete Math. 43 (1983) 23-29, doi: 10.1016/0012-365X(83)90160-7. | Zbl 0508.05058

[007] [8] A. Quilliot, Thèse d'Etat (Université de Paris VI, 1983).

[008] [9] R. Tosić, The search number of the Cartesian product of graphs, Univ. u Novom Sadu, Zb. Rad. Prirod.-Mat. Fak., Ser. Mat. 17 (1987) 239-243. | Zbl 0636.90050