zbMATH — the first resource for mathematics

A game of cops and robbers played on products of graphs. (English) Zbl 0957.91029
Summary: The game of cops and robbers is played with a set of ‘cops’ and a ‘robber’ who occupy some vertices of a graph. Both sides have perfect information and they move alternately to adjacent vertices. The robber is captured if at least one of the cops occupies the same vertex as the robber. The problem is to determine on a given graph, \(G\), the least number of cops sufficient to capture the robber, called the cop-number, \(c(G)\). We investigate this game on three products of graphs: the Cartesian, categorical, and strong products.

91A43 Games involving graphs
05C57 Games on graphs (graph-theoretic aspects)
91A24 Positional games (pursuit and evasion, etc.)
Full Text: DOI
[1] Aigner, M.; Fromme, M., A game of cops and robbers, Discrete appl. math., 8, 1-12, (1984) · Zbl 0539.05052
[2] Andreae, T., On a pursuit game played on graphs for which a minor is excluded, J. combin. theory ser. B, 41, 37-47, (1986) · Zbl 0641.90110
[3] Anstee, R.; Farber, M., On bridged graphs and cop-win graphs, J. combin. theory, 44, 22-28, (1988) · Zbl 0654.05049
[4] Chartrand, G.; Lesniak, L., Graphs and digraphs, (1986), Wadsworth & Brooks/Cole CA · Zbl 0666.05001
[5] Frankl, P., Cops and robbers in graphs with large girth and Cayley graphs, Discrete appl. math., 17, 301-305, (1987) · Zbl 0624.05041
[6] Frankl, P., On a pursuit game on Cayley graphs, Combinatorica, 7, 67-70, (1987) · Zbl 0621.05017
[7] Maamoun, M.; Meyniel, H., On a game of policemen and robber, Discrete appl. math., 17, 307-309, (1987) · Zbl 0615.05049
[8] Neufeld, S., A game of cops and robbers, () · Zbl 0957.91029
[9] Neufeld, S.; Nowakowski, R., A vertex-to-vertex pursuit game played on disjoint sets of edges, (), 299-312 · Zbl 0845.05092
[10] Nowakowski, R.; Winkler, P., Vertex to vertex pursuit in a graph, Discrete math., 43, 230-239, (1983) · Zbl 0508.05058
[11] Quilliot, A., ()
[12] Quilliot, A., A short note about pursuit games played on a graph with a given genus, J. combin. theory ser. B, 38, 89-92, (1985) · Zbl 0586.90104
[13] Tošić, R., The search number of the Cartesian product of graphs, Univ. novom sabu zb. rad. prirod.-mat fak. ser. mat., 17, 239-243, (1987) · Zbl 0636.90050
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.