Distance domination, guarding and covering of maximal outerplanar graphs

Abstract

En este trabajo se introduce la noción de k-vigilancia aplicada a la triangulación de grafos en asociación con k-dominación y k-cobertura. Obtenemos resultados para maximal outerplanar graphs cuando k = 2. Un conjunto S de vértices en una triangulación T es un conjunto 2-vigilante (o un conjunto de vigilancia 2d para abreviar) si cada cara de T tiene un vértice adyacente a un vértice de S. Mostramos que ⌊n/5⌋ (respectivamente ⌊n/4⌋) vértices son suficientes para 2d-vigilar y 2d-dominar (respectivamente 2d-cubrir) cualquier maximal outerplanar graph con n vértices. También mostramos que estas cotas son ajustadas.

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.