Note on a pursuit game played on graphs (Q799702): Difference between revisions

\textit{M. Aigner} and \textit{M. Fromme} [A game of cops and robbers, ibid. 8, 1-12 (1984)] considered a two-person game on finite graphs where m pursuers (cops) try to catch one evader (robber). They asked, with c(G) as the minimum number of cops which are sufficient to catch the robber on G, whether it is true that c(G)\(\leq k\), k the maximum degree of G, holds for each graph. Here the author gives a negative answer constructing for all k, n (\(k\geq 3)\) a k-regular graph G with c(G)\(\geq n\).