An upper bound on the double domination number of trees


J. Amjadi




In a graph $G$, a vertex dominates itself and its neighbors. A set $S$ of vertices in a graph $G$ is a {\em double dominating set} if $S$ dominates every vertex of $G$ at least twice. The {\em double domination number} $\gamma_{\times2}(G)$ is the minimum cardinality of a double dominating set in $G$. The {\em 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 show that for any tree $T$ of order $n\ge 2$, different from $P_4$, $\gamma_{\times2}(T)\le \frac{3a(T)+1}{2}$.