Concepedia

The number of maximal independent sets in connected graphs

Zoltán Füredi

Journal of Graph Theory · 1987 · 112 citations · 6 references

DOI

Concepts

Abstract

Abstract Generalizing a theorem of Moon and Moser, we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50.

References

6

On cliques in graphs

J. W. Moon, Leo Moser · Israel Journal of Mathematics · 1965 · 854 citations

, , +4

The Number of Maximal Independent Sets in a Tree

Herbert S. Wilf · SIAM Journal on Algebraic and Discrete Methods · 1986 · 124 citations

, , +8

A new generalization of the Erdős-Ko-Rado theorem

Péter Frankl, Zoltán Füredi · COMBINATORICA · 1983 · 112 citations

, , +7

Three-graphs without two triples whose symmetric difference is contained in a third

Béla Bollobás · Discrete Mathematics · 1974 · 69 citations

, , +6

AN EXTREMAL PROBLEM IN GRAPH THEORY

H. L. Abbott, D. Hanson, A. C. LIU · The Quarterly Journal of Mathematics · 1980 · 56 citations

, , +4