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 gamma(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 gamma(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 gamma(2)(T) <= (n + n(1))/2. As a consequence of our characterization, we also characterize trees T that achieve equality in this bound. (C) 2013 Elsevier B.V. All rights reserved.