Independent and double domination in trees

Mostafa Blidia, Mustapha Chellali, Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


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 languageEnglish
Pages (from-to)159-173
Number of pages15
JournalUtilitas Mathematica
Publication statusPublished - Jul 2006
Externally publishedYes

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics


Dive into the research topics of 'Independent and double domination in trees'. Together they form a unique fingerprint.

Cite this