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


Adriana Hansberg, Bert Randerath, Lutz Volkmann




For a graph $G$ a subset $D$ of the vertex set of $G$ is a $k$-dominating set if every vertex not in $D$ has at least $k$ neighbors in $D$. The$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 domination number $\gamma(G)$. Fink and Jacobson showed in 1985 that the inequality $\gamma_k(G)\leq\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)$