Survey on counting maximal independent sets

Abstract

Erdos and Moser raised the problem of determining the largest number of maximal independent sets of a general graph of order n and those graphs achieving this maximum value. This problem was solved by Erdos, and later Moon and Moser. Two decades later, the problem was extensively studied for various classes of graphs, including trees, forests, (connected) graphs with at most one cycle, bipartite graphs, connected graphs, k-connected graphs and (connected) triangle-free graphs. This paper surveys results on this and related problems.