The largest number of maximal independent sets in twinkle graphs

Abstract

A maximal independent set is an independent set that is not a proper subset of any other independent set. A twinkle graph W is a connected unicyclic graph with cycle C such that W – x is disconnected for any $x\in V(C)$. In this paper, we determine the largest number of maximal independent sets and characterize those extremal graphs achieving these values among all twinkle graphs. Using the results on twinkle graphs, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs with at most one cycle.