Trees with the Second and Third Largest Number of Maximal Independent Sets

Abstract

Let $G$ be a simple undirected graph. Denote by $mi(G)$ the number of maximal independent sets in $G$. In this paper, we determine the second and third largest number of maximal independent sets in trees. Extremal trees achieving these values are also determined.