A finiteness theorem for maximal independent sets (Q2563420): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Gerard Jennhwa Chang / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: John W. Moon / rank | |||
Normal rank |
Revision as of 10:26, 14 February 2024
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