A Note on Independent Sets in Trees
Bruce E. Sagan · SIAM Journal on Discrete Mathematics · 1988
We give a simple graph-theoretical proof that the largest number of maximal independent vertex sets in a tree with n vertices is given by \[ m( T ) = \begin{cases} 2^{k - 1} + 1& {\text{if }} n = 2k, \\ 2^k & {\text{if }} n = 2k + 1, \end{cases}\] a result first proved by Wilf [SIAM J. Algebraic Discrete Methods, 7 (1986), pp. 125–130]. We also characterize those trees achieving this maximum value. Finally we investigate some related problems.