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

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

Authors: David R. Wood ORCID-iD1

  • 1 Department of Mathematics and Statistics [Melbourne]

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.

https://doi.org/10.46298/dmtcs.543
Source: HAL:hal-00990494v1
Volume: Vol. 13 no. 3
Section: Combinatorics
Published on: September 10, 2011
Accepted on: June 9, 2015
Submitted on: August 17, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.tcs.2006.06.015
  • 10.1016/j.tcs.2006.06.015
The worst-case time complexity for generating all maximal cliques and computational experiments

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 252 times.
This article's PDF has been downloaded 280 times.