On the Equality of Domination Number and 2-Domination Number
Abstract The 2-domination number γ2(G) of a graph G is the minimum cardinality of a set D ⊆ 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.