2021/07/06 by Zhuang, Wei
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2107.02796
In a graph G, a vertex dominates itself and its neighbors. A subset S⊆ V(G) is said to be a double dominating set of G if S dominates every vertex of G at least twice. The double domination number γ× 2(G) is the minimum cardinality of a double dominating set of G. We show that if G is a maximal outerplanar graph on n≥ 3 vertices, then γ× 2(G)≤ \lfloor (2n)/(3)\rfloor. Further, if n≥ 4, then γ× 2(G)≤ min \\lfloor (n+t)/(2)\rfloor, n-t\, where t is the number of vertices of degree 2 in G. These bounds are shown to be tight. In addition, we also study the case that G is a striped maximal outerplanar graph.