##
**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.) |