The numbers of maximal independent sets in connected unicyclic graphs

Abstract

A maximal independent set is an independent set that is not a proper subset of any other independent set. A graph is said to be unicyclic if it contains exactly one cycle. In this paper, we determine the first three largest numbers of maximal independent sets and characterize those extremal graphs achieving these values among all connected unicyclic graphs. Using these results, the problem for the third largest number of maximal independent sets among all (connected) graphs with at most one cycle is also resolved.