Trees with the Fourth Largest Number of Maximal Independent Sets

Abstract

Let $G=(V,E)$ be a simple undirected graph. An independent set is a subset $S\subseteq V$ such that no two vertices in $S$ are adjacent. A maximal independent set is an independent set that is not a proper subset of any other independent set.
In this paper, we study the problem of determining the fourth largest number of maximal independent sets among all trees and forests. Extremal graphs achieving these values are also given.