On the Equality of Domination Number and 2-Domination Number

The 2-domination number gamma(2)(G) of a graph G is the minimum cardinality of a set D subset of 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.