The number of maximal independent sets in a connected graph
type: Item
instance of: scholarly article
title: The number of maximal independent sets in a connected graph
zbMATH Open document ID: 0652.05027
DOI: 10.1016/0012-365X(88)90114-8
author: J. Griggs
author: Charles M. Grinstead
author: David R. Guichard
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: Let \(g(n)\) be the maximum number of maximal independent sets, which a connected graph on \(n\) vertices can have. It is proved that \[ g(n) = \begin{cases} 2.3^{n/3-1} + 2^{n/3-1} \quad&\text{if }n\equiv 0\pmod3 \\ 3^{[n/3]} + 2^{[n/3]-1} \quad&\text{if }n\equiv 1\pmod3 \\ 4.3^{[n/3]-1} + 3.2^{[n/3]-2} \quad&\text{if }n\equiv 2\pmod3. \end{cases} \] All connected graphs with \(g(n)\) maximal independent sets are the following (Theorem 3): \(n\leq 4:\) the complete graphs \(K_ n\); \(n=5:\) The cycle \(C_5\), the complete graph \(K_5\) and the graphs shown in Fig. 1; \(n\geq 6:\) the graphs \(E_ n\) shown in Fig. 2, where the subgraphs \(G_ 1\), \(G_ 2\) are both the triangles or both the complete graphs \(K_ 4\) or \(G_ 1\) is the complete graph \(K_ 4\) and \(G_ 2\) is the triangle. {Remark: The two figures may be looked at in the printed version of Zentralblatt für Mathematik.}
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4063120
zbMATH Keywords: central cutpoint
zbMATH Keywords: block
zbMATH Keywords: cutpoint graph
zbMATH Keywords: pendant block
zbMATH Keywords: penultimate vertex
zbMATH Keywords: block graph
zbMATH Keywords: maximal independent sets
MaRDI profile type: Publication
cites work: Parallel concepts in graph theory
cites work: On cliques in graphs
cites work: A Note on Independent Sets in Trees
cites work: The Number of Maximal Independent Sets in a Tree
description: scientific article; zbMATH DE number 4063120