On the equality of domination number and $2$-domination number

The 2-domination number $γ_2(G)$ of a graph $G$ is the minimum cardinality of a set $D \subseteq V(G)$ for which every vertex outside $D$ is adjacent to at least two vertices in $D$. Clearly, $γ_2(G)$ cannot be smaller than the domination number $γ(G)$. We consider a large class of graphs and characterize those members which satisfy $γ_2=γ$. For the general case, we prove that it is NP-hard to decide whether $γ_2=γ$ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.

No reviews yet.

No comments yet.