Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/21068
Título: | On Cops and Robbers on $G^{\Xi}$ and cop-edge critical graphs |
Autor: | Cardoso, Domingos M. Dominic, Charles Witkowski, Lukasz Witkowski, Marcin |
Palavras-chave: | Cops and Robbers Vertex-pursuit games |
Data: | Dez-2017 |
Editora: | University of Calgary |
Resumo: | 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 |
Versão do Editor: | http://hdl.handle.net/10515/sy5b85419 |
Aparece nas coleções: | CIDMA - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
CardosoDominivLWitkowskiMWitkowski2017.pdf | Main article | 350.18 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.