×

The number of maximal independent sets in triangle-free graphs. (English) Zbl 0779.05025

The authors show that the number of maximal independent sets of vertices in a triangle-free graph \(G\) with \(n\geq 4\) vertices is at most \(2^{n/2}\) or \(5\cdot 2^{(n-5)/2}\), according as \(n\) is even or odd. Equality holds only when \(G\) consists of \(n/2\) disjoint edges or of \((n- 5)/2\) disjoint edges and an isolated 5-cycle.

MSC:

05C35 Extremal problems in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI