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