Characterization of outerplanar graphs with equal 2-domination and domination numbers

Abstract

A {\em $k$-domination number} of a graph $G$ is minimum cardinality of a $k$-dominating set of $G$, where a subset $S \subseteq V(G)$ is a {\em $k$-dominating set} if each vertex $v\in V(G)\setminus S$ is adjacent to at least $k$ vertices in $S$. It is known that for any graph $G$ with $\Delta(G) \geq k \geq 2$, $\gamma_k(G) \geq \gamma(G) + k - 2$, and then $\gamma_k(G) > \gamma(G)$ for any $k\geq 3$, where $\gamma(G) = \gamma_1(G)$ is the usual domination number. Thus, it is the most interesting problem to characterize graphs $G$ with $\gamma_2(G) = \gamma(G)$. In this paper, we characterize outerplanar graphs with equal 2-domination and domination numbers.

Keywords

• 2-domination number
• domination number
• outerplanar graph