The Number of Maximal Independent Sets in Trees and Forests

Abstract

For a simple undirected graph \(G = (V, E)\), a subset \(I\) of \(V(G)\) is said to be an independent set of \(G\) if any two vertices in \(I\) are not adjacent in \(G\). A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we survey the largest to fourth largest numbers of maximal independent sets among all trees and forests. In addition, we further look into the problem of determining the fifth largest number of maximal independent sets among all trees and forests. Extremal graphs achieving these values are also given.