Abstract
For a vertex D of a graph G = (V,E), the domination number γv(G) of G relative to v is the minimum cardinality of a dominating set in G that contains v. The average domination number of G is γav(G) = 1/|V| ∑v∈V(G). The independent domination number iv(G) of G relative to v is the minimum cardinality of a maximal independent set in G that contains v. The average independent domination number of G is iav(G) = 1/|V| ∑v∈V iv(G). In this paper, we show that a tree T satisfies γav(T) = iav(T) if and only if A(T) = Φ or each vertex of A(T) has degree 2 in T, where A(T) is the set of vertices of T that are contained in all its minimum dominating sets.
Original language | English |
---|---|
Pages (from-to) | 305-318 |
Number of pages | 14 |
Journal | Ars Combinatoria |
Volume | 71 |
Publication status | Published - Apr 2004 |
Externally published | Yes |
Keywords
- Average domination
- Average independent domination
- Trees
ASJC Scopus subject areas
- General Mathematics