Convex dominating sets in maximal outerplanar graphs
Magdalena Lemańska , Eduardo Rivera-Campo , Radosław Ziemann , Rita Zuazua , Paweł Żyliński
AbstractIn 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.
|Journal series||Discrete Applied Mathematics, ISSN 0166-218X, (N/A 70 pkt)|
|Publication size in sheets||0.75|
|Keywords in English||convex domination, outerplanar, flipping edge, convex guard set|
|Score||= 70.0, 28-01-2020, ArticleFromJournal|
|Publication indicators||= 0; : 2018 = 1.263; : 2018 = 0.983 (2) - 2018=1.029 (5)|
|Citation count*||1 (2020-02-19)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.