On the equality of domination number and 2 -domination number

Abstract: The 2-domination number

g a m m a_{2} (G)

of a graph

G

is the minimum cardinality of a set

D s u b s e t e q V (G)

for which every vertex outside

D

is adjacent to at least two vertices in

D

. Clearly,

g a m m a_{2} (G)

cannot be smaller than the domination number

g a m m a (G)

. We consider a large class of graphs and characterize those members which satisfy

g a m m a_{2} = g a m m a

. For the general case, we prove that it is NP-hard to decide whether

g a m m a_{2} = g a m m a

holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.

This page was built for publication: On the equality of domination number and $ 2 $-domination number