The number of maximal independent sets in a connected graph (Q1106856)

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.}