The Number of Independent Sets Intersecting the Set of Leaves in Trees

Abstract

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.