The number of maximal independent sets in connected triangle-free graphs (Q1292823)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The number of maximal independent sets in connected triangle-free graphs |
scientific article |
Statements
The number of maximal independent sets in connected triangle-free graphs (English)
0 references
9 August 1999
0 references
The authors show that the maximum number of maximal independent sets possible in a connected triangle-free graph with \(n\geq 22\) nodes is \(5\cdot 2^{(n- 6)/2}\) when \(n\) is even and \(2^{(n- 1)/2}\) when \(n\) is odd. They also characterize the extremal graphs.
0 references
maximal independent sets
0 references
triangle-free graph
0 references
extremal graphs
0 references
