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 the normal view instead:
scientific article; zbMATH DE number 957383
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A finiteness theorem for maximal independent sets |
scientific article; zbMATH DE number 957383 |
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
0.8272223472595215
0 references
0.8238111734390259
0 references
0.8167193531990051
0 references
0.8094204068183899
0 references
