Search

A dominating set of a graph G is a set S ⊆ 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 γ c (G). Zhuang showed that γ c (G) of a maximal outerplanar graph G is bounded by min { ⌊ n + k 2 ⌋ − 2 , ⌊ 2 (n − k) 3 ⌋ } (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 γ c (G) ≤ ⌊ n − k + x 2 ⌋ , where x is a counter in the algorithm and x ≤ k − 2. As a corollary, the result that γ c (G) ≤ ⌊ n − 2 2 ⌋ 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. [ABSTRACT FROM AUTHOR]