Bounds for the connected domination number of maximal outerplanar graphs

A dominating set of a graph G is a set S subset of V(G) such that every vertex in G is either in S or adjacent to a vertex in S. A dominating set S is a connected dominating set if the subgraph of G induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number, denoted by gamma(c)(G). Zhuang showed that gamma(c)(G) of a maximal outerplanar graph G is bounded by min{left perpendicular n+k/2 right perpendicular - 2, left perpendicular 2(n-k)/3 right perpendicular} (Zhuang, 2020), where k is the number of 2-degree vertices in G. In this paper, we give an algorithm for finding a connected dominating set of maximal outerplanar graphs and get an upper bound gamma(c)(G) <= left perpendicular n-k+x/2 right perpendicular, where x is a counter in the algorithm and x <= k - 2. As a corollary, the result that gamma(c)(G) <= left perpendicular n-2/2 right perpendicular for a maximal outerplanar G is gotten directly. This results is better than the above known bound for 3 < k < n+6/4. In addition, we complement some analysis with simulations to evaluate the advantages of our results. (C) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper introduces the concepts of connected dominating sets and their connected domination numbers in graphs, and proposes an algorithm for finding connected dominating sets in maximal outerplanar graphs. An upper bound for the connected domination number of maximal outerplanar graphs is obtained through this algorithm. Additionally, the advantages of the results are evaluated through simulations.