×

On cops and robbers on \(G^{\Xi}\) and cop-edge critical graphs. (English) Zbl 1376.05091

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.

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.)
PDFBibTeX XMLCite