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

Abstract

The 2-domination number ${\gamma }_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, ${\gamma }_2(G)$ cannot be smaller than the domination number $\gamma (G)$. We consider a large class of graphs and characterize those members which satisfy ${\gamma }_2=\gamma$. For the general case, we prove that it is NP-hard to decide whether ${\gamma }_2=\gamma$ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.

Submitted to a journal in July 2018