A tandem version of the cops and robber game played on products of graphs

Nancy E. Clarke; Richard J. Nowakowski

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 3, page 241-249
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Nancy E. Clarke, and Richard J. Nowakowski. "A tandem version of the cops and robber game played on products of graphs." Discussiones Mathematicae Graph Theory 25.3 (2005): 241-249. <http://eudml.org/doc/270333>.

@article{NancyE2005,
abstract = {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.},
author = {Nancy E. Clarke, Richard J. Nowakowski},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {game; cop; tandem-win; pursuit; graph; product},
language = {eng},
number = {3},
pages = {241-249},
title = {A tandem version of the cops and robber game played on products of graphs},
url = {http://eudml.org/doc/270333},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Nancy E. Clarke
AU - Richard J. Nowakowski
TI - A tandem version of the cops and robber game played on products of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 3
SP - 241
EP - 249
AB - 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.
LA - eng
KW - game; cop; tandem-win; pursuit; graph; product
UR - http://eudml.org/doc/270333
ER -

References

top
  1. [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). Zbl0919.05001
  2. [2] N.E. Clarke, Constrained Cops and Robber (Ph.D. Thesis, Dalhousie University, 2002). 
  3. [3] N.E. Clarke and R.J. Nowakowski, Tandem-win Graphs, to appear in Discrete Math. Zbl1073.05060
  4. [4] W. Imrich and H. Izbicki, Associative Products of Graphs, Monatshefte für Mathematik 80 (1975) 277-281, doi: 10.1007/BF01472575. Zbl0328.05136
  5. [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. Zbl0615.05049
  6. [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. Zbl0957.91029
  7. [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. Zbl0508.05058
  8. [8] A. Quilliot, Thèse d'Etat (Université de Paris VI, 1983). 
  9. [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. Zbl0636.90050

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.