zbMATH — the first resource for mathematics

A game of cops and robbers. (English) Zbl 0539.05052
Let G be a finite connected undirected graph. Two players, the cop C and robber R, play a game on G according to the following rules. First C then R occupy some vertex of G. After that they move alternately along edges of G. The cop wins if he succeeds in eventually occupying the same vertex as R, otherwise R wins. A graph G is ”cop-win” if C has a winning strategy; otherwise it is ”robber-win”. R. Novakowski and P. Winkler [Discrete Math. 43, 235-239 (1983; Zbl 0508.05058)] previously gave an algorithmic characterization of cop-win graphs, and showed that this family formed a ”variety” in the sense of closure under (strong) graph products and retractions. The Novakowski-Winkler results are first reviewed, and then the authors generalize the game to a game where a team of n cops chase the robber. The ”cop number” c(G) is defined to be the minimum number of cops required to catch the robber in G. Graphs \(G_ n\) are constructed for which \(c(G_ n)\geq n\), namely n-regular graphs with girth at least 5. The most striking result proved is that c(G)\(\leq 3\) for all planar graphs G.
Reviewer: T.D.Parsons

05C57 Games on graphs (graph-theoretic aspects)
05C75 Structural characterization of families of graphs
91A24 Positional games (pursuit and evasion, etc.)
Full Text: DOI
[1] D. Duffus and I. Rival, Graphs orientable as distributive lattices, Proc. Amer. Math. Soc.
[2] Gal, I., Search games, (1982), Addison-Wesley Reading, MA
[3] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[4] Nowakowski, R.; Rival, I., The smallest graph variety containing all paths, Discrete math., 43, 223-234, (1983) · Zbl 0511.05059
[5] Nowakowski, R.; Winkler, R.P., Vertex-to-vertex pursuit in a graph, Discrete math., 43, 235-239, (1983) · Zbl 0508.05058
[6] Parsons, T.D., Pursuit-evasion in a graph, (), 426-441 · Zbl 0379.05026
[7] Parsons, T.D., The search number of a connected graph, Proc. 9th south-eastern conf. on combinatorics graph theory and computing, 549-554, (1978) · Zbl 0418.05022
[8] A. Quilliot, Discrete pursuit games on graphs and metric spaces, to appear. · Zbl 0615.90108
[9] Smith, C.A.B., Graphs and composite games, J. combin. theory, 1, 51-81, (1968) · Zbl 0141.36101
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.