Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/15346
Title: | Distance domination, guarding and covering of maximal outerplanar graphs |
Author: | Canales, Santiago Hernández, Gregorio Martins, Mafalda Matos, Inês |
Keywords: | Domination Covering Guarding Triangulation graphs |
Issue Date: | 30-Jan-2015 |
Publisher: | Elsevier |
Abstract: | 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 |
Appears in Collections: | CIDMA - Artigos OGTCG - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Distance domination, guarding and vertex cover for maximal outerplanar graphs.pdf | Documento Principal | 497.69 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.