arXiv Analytics

Sign in

arXiv:1104.1243 [math.CO]AbstractReferencesReviewsResources

On the number of maximal independent sets in a graph

David R. Wood

Published 2011-04-07, updated 2011-04-14Version 2

Miller and Muller (1960) and independently Moon and Moser (1965) determined the maximum number of maximal independent sets in an $n$-vertex graph. We give a new and simple proof of this result.

Journal: Discrete Maths. & Theoretical Computer Science 13.3:17-20, 2011
Categories: math.CO, cs.DM
Related articles: Most relevant | Search more
arXiv:1610.06058 [math.CO] (Published 2016-10-19)
Coverings, Matchings and the number of maximal independent sets of graphs
arXiv:math/0207100 [math.CO] (Published 2002-07-11, updated 2005-04-30)
Maximal Independent Sets In Graphs With At Most r Cycles
arXiv:2108.06359 [math.CO] (Published 2021-08-13)
Maximal independent sets in clique-free graphs

Links

Toolbox