Dominating Sets and Independent Sets in a Tree

Abstract

The domination number \(\gamma(G)\) of a graph \(G\) is the minimum cardinality among all dominating sets of \(G\), and the independence number \(\alpha(G)\) of \(G\) is the maximum cardinality among all independent sets of \(G\). For any graph \(G\), it is easy to see that \(\gamma(G) \leq \alpha(G)\). In this paper, we present a characterization of trees \(T\) with \(\gamma(T) = \alpha(T)\).