Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/15346
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Canales, Santiago | pt |
dc.contributor.author | Hernández, Gregorio | pt |
dc.contributor.author | Martins, Mafalda | pt |
dc.contributor.author | Matos, Inês | pt |
dc.date.accessioned | 2016-03-22T10:22:02Z | - |
dc.date.issued | 2015-01-30 | - |
dc.identifier.issn | 0166-218X | pt |
dc.identifier.uri | http://hdl.handle.net/10773/15346 | - |
dc.description.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. | pt |
dc.language.iso | eng | pt |
dc.publisher | Elsevier | pt |
dc.relation | PEst-C/MAT/UI4106/2011, FCOMP-01-0124-FEDER-02269 | pt |
dc.relation | FCT - SFRH/BPD/66431/2009 | pt |
dc.relation | FCT - SFRH/BPD/66572/2009 | pt |
dc.relation | EuroGIGA – ComPoSe IP04 – MICINN Project EUI-EURC-2011-4306 | pt |
dc.rights | restrictedAccess | por |
dc.subject | Domination | pt |
dc.subject | Covering | pt |
dc.subject | Guarding | pt |
dc.subject | Triangulation graphs | pt |
dc.title | Distance domination, guarding and covering of maximal outerplanar graphs | pt |
dc.type | article | pt |
dc.peerreviewed | yes | pt |
ua.distribution | international | pt |
degois.publication.firstPage | 41 | pt |
degois.publication.lastPage | 49 | pt |
degois.publication.title | Discrete Applied Mathematics | pt |
degois.publication.volume | 181 | pt |
dc.date.embargo | 10000-01-01 | - |
dc.identifier.doi | 10.1016/j.dam.2014.08.040 | pt |
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.