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 | Size | Format | |
---|---|---|---|---|
CardosoDominivLWitkowskiMWitkowski2017.pdf | Main article | 350.18 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.