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.


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: DOI