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 SizeFormat 
Distance domination, guarding and vertex cover for maximal outerplanar graphs.pdfDocumento Principal497.69 kBAdobe PDF    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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