The characterization of the family for which the domination number is equal to the independence.

This proof was published however the paper was not published electronically so I proved it for myself. I am not really sure how they proved it originally.

Definitions

  • $\alpha(G)$ is the independence number.
  • $\gamma(G)$ is the domination number.
  • $\widehat{T}$ of a tree T is a new tree created from T by adding one new leaf to each of its vertices.

Theorem

The family of trees for which $\alpha(T)=\gamma(T)$ are exactly those in the form of $T=\widehat{H}$ where H is some tree.

Proof

The equivalency will be proved as two implications.

$T=\widehat{H} \Rightarrow \alpha(T)=\gamma(T)$

The tree T has exactly $\frac{|V(T)|}{2}$ leaves and no two leaves are connected to the same inner vertex. Independence number and the domination number of this tree is exactly $\frac{|V(T)|}{2}$. We can pick both sets as the set of all leaves. Independent set cannot be bigger because the graph is connected and $|V(T)|/2$ is the upper bound. Domination set cannot be lower because each leaf must be dominated.

$!(T=\widehat{H}) \Rightarrow !(\alpha(T)=\gamma(T))$

Assume the tree T is not in the right form then there are inner vertices which are either connected to two leaves or to no leaf at all. Root the tree in arbitrary inner node which does not have exactly one leaf. Iteratively remove vertices with only one leaf until we have no such vertex.