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, Charles
Witkowski, Lukasz
Witkowski, Marcin
Keywords: Cops and Robbers
Vertex-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) \text{ or } 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 
CardosoDominivLWitkowskiMWitkowski2017.pdfMain article350.18 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.