Hujter, Mihály; Tuza, Zsolt The number of maximal independent sets in triangle-free graphs. (English) Zbl 0779.05025 SIAM J. Discrete Math. 6, No. 2, 284-288 (1993). 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. Reviewer: J.W.Moon (Edmonton) Cited in 2 ReviewsCited in 51 Documents 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 Keywords:extremal graphs; bound; maximal independent vertices; triangle-free graph PDFBibTeX XMLCite \textit{M. Hujter} and \textit{Z. Tuza}, SIAM J. Discrete Math. 6, No. 2, 284--288 (1993; Zbl 0779.05025) Full Text: DOI