Coverings, Matchings and the number of maximal independent sets of graphs
arXiv:1610.06058
Abstract
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 König-Egerváry graphs in terms of their matching numbers.
7 pages, 1 figure