Claw-Free Graphs with Equal 2-Domination and Domination Numbers

Abstract

For a graph $G$ a subset $D$ of the vertex set of $G$ is a {\it $k$-dominating set} if every vertex not in $D$ has at least $k$ neighbors in $D$. The {\it $k$-domination number} $\gamma_k(G)$ is the minimum cardinality among the $k$-dominating sets of $G$. Note that the 1-domination number $\gamma_1(G)$ is the usual {\it domination number} $\gamma(G)$. Fink and Jacobson showed in 1985 that the inequality $\gamma_k(G) \ge \gamma(G) + k - 2$ is valid for every connected graph $G$. In this paper, we concentrate on the case $k=2$, where $\gamma_k$ can be equal to $\gamma$, and we characterize all claw-free graphs and all line graphs $G$ with $\gamma(G) = \gamma_2(G)$.