Double domination in maximal outerplanar graphs

Abstract

In graph GG, a vertex dominates itself and its neighbors. A subset S⊆V(G)S\subseteq V\left(G) is said to be a double-dominating set of GG if SS dominates every vertex of GG at least twice. The double domination number γ×2(G){\gamma }_{\times 2}\left(G) is the minimum cardinality of a double dominating set of GG. We show that if GG is a maximal outerplanar graph on n≥3n\ge 3 vertices, then γ×2(G)≤2n3{\gamma }_{\times 2}\left(G)\le ⌊\frac{2n}{3}⌋. Further, if n≥4n\ge 4, then γ×2(G)≤minn+t2,n−t{\gamma }_{\times 2}\left(G)\le \min \left\{⌊\frac{n+t}{2}⌋,n-t\right\}, where tt is the number of vertices of degree 2 in GG. These bounds are shown to be tight. In addition, we also study the case that GG is a striped maximal outerplanar graph.

Keywords

• maximal outerplanar graph
• striped maximal outerplanar graph
• double domination
• 05c69