Relating the annihilation number and the 2-domination number of a tree

A set S of vertices in a graph G is a 2-dominating set if every vertex of G not in S is adjacent to at least two vertices in S . The 2-domination number γ 2 ( G ) is the minimum cardinality of a 2-dominating set in G . The annihilation number a ( G ) is the largest integer k such that the sum of the first k terms of the nondecreasing degree sequence of G is at most the number of edges in G . The conjecture-generating computer program, Graffiti.pc, conjectured that γ 2 ( G ) ≤ a ( G ) + 1 holds for every connected graph G . It is known that this conjecture is true when the minimum degree is at least 3. The conjecture remains unresolved for minimum degree 1 or 2. In this paper, we prove that the conjecture is indeed true when G is a tree, and we characterize the trees that achieve equality in the bound. It is known that if T is a tree on n vertices with n 1 vertices of degree 1, then γ 2 ( T ) ≤ ( n + n 1 ) / 2 . As a consequence of our characterization, we also characterize trees T that achieve equality in this bound.