Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/21068
 Title: On Cops and Robbers on $G^{\Xi}$ and cop-edge critical graphs Author: Cardoso, Domingos M.Dominic, CharlesWitkowski, LukaszWitkowski, Marcin Keywords: Cops and RobbersVertex-pursuit games Issue Date: Dec-2017 Publisher: University of Calgary Abstract: Cop Robber game is a two player game played on an undirected graph. In this game cops try to capture a robber moving on the vertices of the graph. The cop number of a graph is the least number of cops needed to guarantee that the robber will be caught. In this paper we presents 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})\leq 3$. 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)$. We show couple examples of cop-edge critical graphs having cop number equal to $3$. Peer review: yes URI: http://hdl.handle.net/10773/21068 ISSN: 1715-0868 Publisher Version: http://hdl.handle.net/10515/sy5b85419 Appears in Collections: CIDMA - Artigos

Files in This Item:
File Description SizeFormat