### Abstrakt

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.

Originalsprog | Engelsk |
---|---|

Tidsskrift | Discrete Mathematics |

Vol/bind | 319 |

Sider (fra-til) | 15-23 |

ISSN | 0012-365X |

DOI | |

Status | Udgivet - 2014 |

Udgivet eksternt | Ja |

### Fingerprint

### Citationsformater

*Discrete Mathematics*,

*319*, 15-23. https://doi.org/10.1016/j.disc.2013.11.020