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)\le \alpha (G)$. In this paper, we present a characterization of trees $T$ with $\gamma (T)=\alpha (T)$.