A subset \(S \subseteq V(G)\) is independent if no two vertices of \(S\) are adjacent in \(G\). In this paper we study the number of independent sets which meets the set of leaves in a tree. In particular we determine the smallest number and the largest number of these sets among \(n\)-vertex trees. In each case we characterize the extremal graphs.
Citation
Iwona Wloch, Andrzej Wloch. The Number of Independent Sets Intersecting the Set of Leaves in Trees[J], Ars Combinatoria, Volume 085. 225-231. .