A finiteness theorem for maximal independent sets (Q2563420): Difference between revisions

Let \(G\) denote a graph with no isolated vertices and with no two vertices that have the same neighbourhood. The authors show, among other things, that if \(G\) has exactly \(k\) maximal independent sets of vertices, where \(k\geq 2\), then \(G\) has at most \(2^{k-1} + k-2\) vertices.