Qiao, Hong; Kang, Liying; Cardei, Mihaela; Du, Ding-Zhu Paired-domination of trees. (English) Zbl 1013.05055 J. Glob. Optim. 25, No. 1, 43-54 (2003). Summary: Let \(G= (V, E)\) be a graph without isolated vertices. A set \(S\subseteq V\) is a paired-dominating set if it dominates \(V\) and the subgraph induced by \(S\) contains a perfect matching. The paired-domination number \(\gamma_p(G)\) is defined to be the minimum cardinality of a paired-dominating set \(S\) in \(G\). In this paper, we present a linear-time algorithm computing the paired-domination number for trees and characterize trees with equal domination and paired-domination numbers. Cited in 1 ReviewCited in 43 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C05 Trees 05C75 Structural characterization of families of graphs PDFBibTeX XMLCite \textit{H. Qiao} et al., J. Glob. Optim. 25, No. 1, 43--54 (2003; Zbl 1013.05055) Full Text: DOI