An upper bound for the number of maximal independent sets in a graph
Vladimir Evgen'evich Alekseev · Discrete Mathematics and Applications · 2007
Let T ( G ) be the number of maximal independent sets, M ( G ) be the number of generated matchings in a graph G . We prove the inequality T ( G ) ≤ M ( G ) + 1. As a corollary, we derive the bound for a graph containing no generated subgraph ( p + 1) K 2 , where m is the number of edges and m 1 is the number of dominating edges. This inequality differs from the Balas–Yu conjecture only in the presence of the last term.