Moreira Cardoso, Domingos; Dominic, Charles; Witkowski, Łukasz; Witkowski, Marcin On cops and robbers on \(G^{\Xi}\) and cop-edge critical graphs. (English) Zbl 1376.05091 Contrib. Discrete Math. 12, No. 2, 167-186 (2017). Summary: Cops and Robbers is a two player game played on an undirected graph. In this game the cops try to capture a robber moving on the vertices of a graph. The cop number of a graph, denoted by \(c(G)\), is the least number of cops needed to guarantee that the robber will be caught. In this paper we present results concerning games on \(G^{\Xi}\), that is the graph obtained by connecting the corresponding vertices in \(G\) and its complement \(\overline{G}\). In particular we show that for planar graphs \(c(G^\Xi)\leq3\). Furthermore we investigate the cop edge-critical graphs, i.e. graphs that for any edge \(e\) in \(G\) we have either \(c(G-e)<c(G)\) or \(c(G-e)>c(G)\). We show a couple of examples of cop edge-critical graphs having cop number equal to 3. Cited in 1 Document MSC: 05C57 Games on graphs (graph-theoretic aspects) 05C80 Random graphs (graph-theoretic aspects) 05C10 Planar graphs; geometric and topological aspects of graph theory 91A43 Games involving graphs 91A24 Positional games (pursuit and evasion, etc.) Keywords:cops and robbers; vertex-pursuit games PDFBibTeX XMLCite \textit{D. Moreira Cardoso} et al., Contrib. Discrete Math. 12, No. 2, 167--186 (2017; Zbl 1376.05091)