## Paired-domination in graphs.(English)Zbl 0997.05074

Summary: In a graph $$G= (V,E)$$ if we think of each vertex $$s$$ as the possible location for a guard capable of protection each vertex in its closed neighborhood $$N[s]$$, then “domination” requires every vertex to be protected. Thus, $$S\subset V(G)$$ is a dominating set if $$\bigcup_{s\in s}N[s]= V(G)$$. For total domination, each guard must, in turn, be protected, so we would want $$\bigcup_{s\in S}N(s)= V(G)$$. The (total) domination number $$\gamma(G)$$ $$(\gamma_t(G))$$ is the minimum cardinality taken over all minimal (total) dominating sets of $$G$$. We introduce paired-domination for which each guard is assigned another adjacent one, and they are designated a backups for each other, that is, a paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. We show that the paired-domination problem is NP-complete and present bounds on the paired-domination number $$\gamma_p(G)$$. This paper also contains results relating $$\gamma_p(G)$$ to other domination parameters. For example, we note that $$\gamma(G)\leq \gamma_t(G)\leq \gamma_p(G)$$ and characterize those triples $$(a,b,c)$$ of positive integers $$a\leq b\leq c$$ for which there is a graph $$G$$ having $$\gamma(G)= a$$, $$\gamma_t(G)=b$$, and $$\gamma_p(G)= c$$. In addition, we introduce the concept of strong equality of parameters.

### MSC:

 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: