Graphs with the second largest number of maximal independent sets

Let G be a simple undirected graph. Denote by mi(G) (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erdos and Moser raised the problem of determining the maximum value of mi(G) among all graphs of order it 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 r cycles. In this paper we determine the second largest value of mi(G) and xi(G) among all graphs of order it. Moreover, the extremal graphs achieving these values are also determined. (C) 2007 Elsevier B.V. All rights reserved.