CONSTRAINTS ON THE NUMBER OF MAXIMAL INDEPENDENT SETS IN GRAPHS

A maximal independent set of a graph G is an independent set that is n ot contained properly in any other independent set of G. Let i(G) deno te the number of maximal independent sets of G. Here, we prove two con jectures, suggested by P. Erdos, that the maximum number of maximal in dependent sets among all graphs of order n in a family Phi is o(3(n/3) ) if Phi is either a family of connected graphs such that the largest value of maximum degrees among all graphs of order n in Phi is o(n) or a family of graphs such that the minimum value of the lengths of long est paths among all graphs of order n in Phi approaches infinity as n --> infinity. (C) 1994 John Wiley & Sons, Inc.