A finiteness theorem for maximal independent sets (Q2563420)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A finiteness theorem for maximal independent sets |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A finiteness theorem for maximal independent sets |
scientific article |
Statements
A finiteness theorem for maximal independent sets (English)
0 references
12 December 1996
0 references
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.
0 references
maximal independent sets
0 references
