A game of cops and robbers (Q793755): Difference between revisions

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''. \textit{R. Novakowski} and \textit{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.