Bounding the Paired-Domination Number of a Tree in Terms of Its Annihilation Number

Nasrin Dehgardi, Seyed Mahmoud Sheikholeslami, Abdollah Khodkar

A paired-dominating set of a graph $G=(V,E)$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $G$, denoted by $\gamma_{pr}(G)$, is the minimum cardinality of a paired-dominating set of $G$. The annihilation number $a(G)$ is the largest integer $k$ such that the sum of the first $k$ terms of the non-decreasing degree sequence of $G$ is at most the number of edges in $G$. In this paper, we prove that for any tree $T$ of order $n\geq2,\gamma_{pr}(T)\leq\frac{4a(T)+2}3$ and we characterize the trees achieving this bound.