A finiteness theorem for maximal independent sets

Abstract

Denote by mi(G) the number of maximal independent sets of G. This paper studies the set S(k) of all graphs G with mi(G) = k and without isolated vertices (except G congruent to K-1) or duplicated vertices. We determine S(1), S(2), and S(3) and prove that V(G) less than or equal to 2(k-1) + k - 2 for any G in S(k) and k greater than or equal to 2; consequently, S(k) is finite for any k.