×

zbMATH — the first resource for mathematics

The number of maximal independent sets in connected graphs. (English) Zbl 0647.05032
Generalizing a theorem of J. W. Moon and L. Moser [Isr. J. Math. 3, 23-28 (1965; Zbl 0144.232)], we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., \(n>50\).

MSC:
05C35 Extremal problems in graph theory
05C30 Enumeration in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bollobás, Discrete Math. 8 pp 21– (1974)
[2] Frankl, Combinatorica 3 pp 341– (1983)
[3] Frankl, Eur. J. Combinat. 5 pp 127– (1984) · Zbl 0546.05049 · doi:10.1016/S0195-6698(84)80025-6
[4] Extremal problems for hypergraphs. In Combinatorics and , Eds., Mathematics Centre Tracts 56, Amsterdam (1974), part 2, 13–42.
[5] Moon, Isr. J. Math. 3 pp 23– (1965)
[6] Sidorenko, U. D. K. 519 pp 1–
[7] Turán, Mat. Fiz. Lapok 48 pp 436– (1941)
[8] de Caen, Congressus Numerantium 47 pp 249– (1985)
[9] Griggs, Discrete Math.
[10] Wilf, SIAM J. Alg. Disc. Meth. 7 pp 125– (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.