Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0997.05074
Haynes, Teresa W.; Slater, Peter J.
Paired-domination in graphs.
(English)
[J] Networks 32, No.3, 199-206 (1998). ISSN 0028-3045; ISSN 1097-0037/e

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)\le \gamma_t(G)\le \gamma_p(G)$ and characterize those triples $(a,b,c)$ of positive integers $a\le b\le 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 2000:
*05C69 Dominating sets, independent sets, cliques
05C70 Factorization, etc.

Keywords: total domination; domination number; perfect matching; paired-domination number; strong equality

Highlights
Master Server