Independent and Double Domination in Trees
Document Type
Article
Publication Date
7-1-2006
Description
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.
Citation Information
Blidia, Mostafa; Chellali, Mustapha; Haynes, Teresa W.; and Henning, Michael A.. 2006. Independent and Double Domination in Trees. Utilitas Mathematica. Vol.70 159-173. ISSN: 0315-3681