Advanced Search

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

Cited in: Zbl 1226.05086 Zbl 1210.05099 Zbl 1213.05196 Zbl 1174.05093 Zbl 1181.05070 Zbl 1125.05072 Zbl 1108.05069

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]