TOTAL AND PAIRED-DOMINATION NUMBERS OF A TREE
Mustapha Chellali, Teresa W. Haynes, Wayne Goddard · AKCE International Journal of Graphs and Combinatorics · 2004
A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S . A paired-dominating set of G is a dominating set whose induced subgraph has a perfect matching. The minimum cardinality of a total dominating set (respectively, a paired-dominating set) is the total domination number t(G) (respectively, the paired-domination number pr(G) ). We give sharp upper bounds on the total and paired-domination numbers of trees that improve known bounds for some cases. In particular, we show that for a tree T with order n 3 and s support vertices, pr(T) 6 t(T) + s 1 , t(T) (n + s)/2 , and pr(T) (n + 2s 1)/2 .