A note on domination number in maximal outerplanar graphs

A set D subset of V(G) of a graph G is a dominating set if every vertex in V(G)\D has a neighbor in D. The minimum cardinality of a dominating set of G is the domination number of G, denoted by gamma(G). Let G be a maximal outerplanar graph of order n. The authors, in the article On dominating sets of maximal outerplanar and planar graphs. Discrete Applied Mathematics, 198(2016):164-169, proved that gamma(G) <= left perpendicular k+n/4 right perpendicular when k > 0, where k is the number of bad vertices. However, we found that this result is incomplete. In this note, we construct a class A(n) of order n maximal outerplanar graphs such that k = 1 and gamma(G) > left perpendicular k+n/4 right perpendicular . In addition, we show that the upper bound left perpendicular k+n/4 right perpendicular holds for every order n maximal outerplanar graph G satisfying k > 0 and G is not an element of A(n), which improves the previous conclusion. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This article investigates the dominating set problem in maximal outerplanar and planar graphs, revealing the incompleteness of previous results and providing improved conclusions for the problem.