Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/15346
Título: | Distance domination, guarding and covering of maximal outerplanar graphs |
Autor: | Canales, Santiago Hernández, Gregorio Martins, Mafalda Matos, Inês |
Palavras-chave: | Domination Covering Guarding Triangulation graphs |
Data: | 30-Jan-2015 |
Editora: | Elsevier |
Resumo: | In this paper we introduce the notion of distance k-guarding applied to triangulation graphs, and associate it with distance k-domination and distance k-covering. We obtain results for maximal outerplanar graphs when k=2. A set S of vertices in a triangulation graph T is a distance 2-guarding set (or 2d-guarding set for short) if every face of T has a vertex adjacent to a vertex of S. We show that ⌊n/5⌋ (respectively, ⌊n/4⌋) vertices are sufficient to 2d-guard and 2d-dominate (respectively, 2d-cover) any n-vertex maximal outerplanar graph. We also show that these bounds are tight. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/15346 |
DOI: | 10.1016/j.dam.2014.08.040 |
ISSN: | 0166-218X |
Aparece nas coleções: | CIDMA - Artigos OGTCG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Distance domination, guarding and vertex cover for maximal outerplanar graphs.pdf | Documento Principal | 497.69 kB | Adobe PDF |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.