Trees with Equal Average Domination and Independent Domination Numbers

Abstract

For a vertex \(v\) of a graph \(G = (V, E)\), the domination number \(\gamma(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 \(\gamma_{av}(G) = \frac{1}{|V|} \sum_{v\in V} \gamma_v(G)\). The independent domination number \(i_v(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 \(\gamma_{av}^i(G) = \frac{1}{|V|} \sum_{v\in V} i_v(G)\). In this paper, we show that a tree \(T\) satisfies \(\gamma_{av}(T) = i_{av}(T)\) if and only if \(A(T) = \vartheta\) 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.