Abstract
In a graph G, a vertex dominates itself and its neighbors. A subset S of vertices of G is a double dominating set if every vertex in G is dominated at least twice by the vertices of S. The minimum cardinality of a double dominating set of G is the double domination number. We determine sharp lower and upper bounds on the double domination number of a nontrivial tree, and characterize the trees attaining the bounds. As a consequence of these upper bounds, we are able to improve known bounds on the independent domination number of a tree.
| Original language | English |
|---|---|
| Pages (from-to) | 159-173 |
| Number of pages | 15 |
| Journal | Utilitas Mathematica |
| Volume | 70 |
| Publication status | Published - Jul 2006 |
| Externally published | Yes |
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics