×

Paired-domination of trees. (English) Zbl 1013.05055

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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C05 Trees
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI