The second largest number of maximal independent sets in graphs with at most two cycles

摘要

A maximal independent set is an independent set that is not a propersubset of any other independent set. Jou and Chang determined thelargest number of maximal independent sets among all graphs and con-nected graphs of order n, which contain at most one cycle. Later B. E.Sagan and V. R. Vatter found the largest number of maximal indepen-dent sets among all graphs of order n, which contain at most r cycles.In 2012, Jou settled the second largest number of maximal independentsets in graphs with at most one cycle. In this paper, we study the secondlargest number of maximal independent sets among all graphs of ordern 5 with at most two cycles. We also characterize those extremalgraphs achieving these values.