Maximizing the number of maximal independent sets of a fixed size

Chunwei Song, Bowen Yao

Published 2020-12-11, updated 2020-12-19Version 2

For a fixed graph G, a maximal independent set is an independent set that is not a proper subset of any other independent set. P. Erd\"os, and independently, J. W. Moon and L. Moser, and R. E. Miller and D. E. Muller, determined the maximum number of maximal independent sets in a graph on n vertices, as well as the extremal graphs. In this paper we maximize the number of maximal independent sets of a fixed size for all graphs of order n and determine the extremal graphs. Our result generalizes the classical result.