## Abstract

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 ^{n1} vertices of degree 1, then ^{γ2}(T)≤(n+^{n1})/2. As a consequence of our characterization, we also characterize trees T that achieve equality in this bound.

Original language | English |
---|---|

Pages (from-to) | 15-23 |

Number of pages | 9 |

Journal | Discrete Mathematics |

Volume | 319 |

Issue number | 1 |

DOIs | |

Publication status | Published - 28 Mar 2014 |

## Keywords

- 2-domination
- 2-domination number
- Annihilation number

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics