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.
Citation
Jenq-Jong Lin, Min-Jen Jou . Trees with the Fourth Largest Number of Maximal Independent Sets[J], Ars Combinatoria, Volume 109. 299-308. .