Paired domination in trees (Q2159733)

Let \(G\) be a graph with no isolated vertex. A paired-dominating set of \(G\) is a dominating set whose induced subgraph has a perfect matching. The paired-domination number, \(\gamma_{pr}(G)\), of \(G\) is the minimum cardinality among all paired-dominating sets of \(G\). We denote by \(\gamma(G)\) and \(\gamma_t(G)\) the domination number and the total domination number of \(G\), respectively. \textit{T. W. Haynes} and \textit{P. J. Slater} [Networks 32, No. 3, 199--206 (1998; Zbl 0997.05074)] introduced the notion of a paired-dominating set and the paired-domination number of a graph, and they showed that \(\gamma(G) \le \gamma_t(G) \le \gamma_{pr}(G) \le 2\gamma(G)\). Let \(T\) be a tree of order \(n\ge2\). Many results on \(\gamma_{pr}(T)\) have been obtained by several authors, and we list some of them in this review. Let \(\Delta\) denote the maximum among the degrees of vertices, \(n_i\) denote the number of degree \(i\) vertices, and \(s\) denote the number of vertices that are adjacent to some vertices of degree one in \(T\). \textit{H. Qiao} et al. [J. Glob. Optim. 25, No. 1, 43--54 (2003; Zbl 1013.05055)] provided a linear-time algorithm for computing \(\gamma_{pr}(T)\) and they characterized \(T\) satisfying \(\gamma(T)=\gamma_{pr}(T)\). \textit{M. Chellali} and \textit{T. W. Haynes} [AKCE Int. J. Graphs Comb. 1, No. 2, 69--75 (2004; Zbl 1066.05101)] showed that, for \(n\ge3\), \(\gamma_{pr}(T) \le \gamma_t(T)+ s-1\) and \(\gamma_{pr}(T) \le \frac{n+2s-1}{2}\). \textit{J. Raczek} [Australas. J. Comb. 34, 343--347 (2006; Zbl 1105.05054)] showed that \(\gamma_{pr}(T) \ge \frac{n+2-n_1}{2}\). \textit{N. Dehgardi} et al. [Filomat 28, No. 3, 523--529 (2014; Zbl 1464.05283)] showed that \(\gamma_{pr} (T) \le \frac{4a(T)+2}{3}\), where \(a(T)\) is the largest integer \(k\) such that the sum of the first \(k\) terms of the non-decreasing degree sequence of \(T\) is at most the number of edges in \(T\). The authors of the present paper prove that \(\gamma_{pr}(T)\le(\frac{5\Delta-4}{8\Delta-4})n+\frac{1}{2}n_1+\frac{1}{4}n_2-(\frac{\Delta-2}{4\Delta-2})\) and that \(\gamma_{pr}(T) \le 2\alpha(T)-\phi(T)\), where \(\alpha(T)\) denotes the independence number of \(T\) and \(\phi(T)\) denotes the maximum cardinality among collections of vertex-disjoint \(P_3\)'s (3-paths) each of which contains at least a vertex of degree one in \(T\).