Wood, David, - On the number of maximal independent sets in a graph

dmtcs:543 - Discrete Mathematics & Theoretical Computer Science, September 10, 2011, Vol. 13 no. 3
On the number of maximal independent sets in a graph

Authors: Wood, David,

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.


Source : oai:HAL:hal-00990494v1
Volume: Vol. 13 no. 3
Section: Combinatorics
Published on: September 10, 2011
Submitted on: August 17, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 42 times.
This article's PDF has been downloaded 37 times.