Disjoint dominating and 2-dominating sets in graphs

Abstract

A graph $G$ is a $D{D}_2$-graph if it has a pair $(D,D_2)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $D_2$ is a 2-dominating set of $G$. We provide several characterizations and hardness results concerning $D{D}_2$-graphs.

15 pages, 3 figures