Paired-domination of Trees

摘要

Let G = (V, E) be a graph without isolated vertices. A set S is contained in V is a paired-dominating set if it dominates V and the subgraph induced by S, , contains a perfect matching. The paired-domination number γ_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.