Coverings, Matchings and the number of maximal independent sets of graphs


الملخص بالإنكليزية

We determine the maximum number of maximal independent sets of arbitrary graphs in terms of their covering numbers and we completely characterize the extremal graphs. As an application, we give a similar result for Konig-Egervary graphs in terms of their matching numbers.

تحميل البحث