×

Trees with large paired-domination number. (English) Zbl 1112.05078

A paired-dominating set of a graph is a dominating set of vertices whose induced subgraph contains a perfect matching. If \(G\) is a graph without isolated vertices, then it is easy to see that the paired-domination number of \(G\) is bounded above by twice the domination number of \(G\). The authors present a constructive characterization of those trees attaining this bound.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C05 Trees
PDF BibTeX XML Cite