Paired Domination in Trees

A set S of vertices in a graph G is a paired dominating set if every vertex of G is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching (not necessarily as an induced subgraph). The paired domination number, γ_pr(G) , of G is the minimum cardinality of a paired dominating set of G. In this paper, we show that if T is a tree of order at least 2, then γ_pr(T) ≤ 2 α(T) - φ(T) where α(T) is the independence number and φ(T) is the P₃-packing number. We present a tight upper bound on the paired domination number of a tree T in terms of its maximum degree Δ. For Δ≥ 1 , we show that if T is a tree of order n with maximum degree Δ, then γpr(T)≤(5Δ-48Δ-4)n+12n1(T)+14n2(T)-(Δ-24Δ-2), where n₁(T) and n₂(T) denote the number of vertices of degree 1 and 2, respectively, in T. Further, we show that this bound is tight for all Δ≥ 3. As a consequence of this result, if T is a tree of order n≥ 2 , then γpr(T)≤58n+12n1(T)+14n2(T), and this bound is asymptotically best possible.