Convex dominating sets in maximal outerplanar graphs

Magdalena Lemańska , Eduardo Rivera-Campo , Radosław Ziemann , Rita Zuazua , Paweł Żyliński

Abstract

In this paper, we study the concept of convex domination in maximal outerplanar graphs. For this class of graphs, we discuss several properties of this domination parameter, in particular, we provide upper bounds on the convex domination number and study effects on the convex domination number when a maximal outerplanar graph is modified by flipping a diagonal. We also propose a linear time algorithm for computing a minimum convex dominating set in a given maximal outerplanar graph. In addition, we consider the concept of convex guard sets in maximal outerplanar graphs and simple polygons.
Author Magdalena Lemańska
Magdalena Lemańska,,
-
, Eduardo Rivera-Campo
Eduardo Rivera-Campo,,
-
, Radosław Ziemann (FMPI / II)
Radosław Ziemann,,
- Institute of Informatics
, Rita Zuazua
Rita Zuazua,,
-
, Paweł Żyliński (FMPI / II)
Paweł Żyliński,,
- Institute of Informatics
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X, (N/A 70 pkt)
Issue year2019
Vol265
Pages142-157
Publication size in sheets0.75
Keywords in Englishconvex domination, outerplanar, flipping edge, convex guard set
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
DOIDOI:10.1016/j.dam.2019.02.029
URL https://doi.org/10.1016/j.dam.2019.02.029
Languageen angielski
Score (nominal)70
ScoreMinisterial score = 70.0, 30-09-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.17; WoS Impact Factor: 2017 = 0.932 (2) - 2017=1.008 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back