Graphs with the second largest number of maximal independent sets

Let GG be a simple undirected graph. Denote by mi(G) (respectively, xi(G)xi(G)) the number of maximal (respectively, maximum) independent sets in GG. Erdős and Moser raised the problem of determining the maximum value of mi(G) among all graphs of order nn and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most rr cycles. In this paper we determine the second largest value of mi(G) and xi(G)xi(G) among all graphs of order nn. Moreover, the extremal graphs achieving these values are also determined.