The number of maximal independent sets of \((k+1)\)-valent trees (Q2504102)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The number of maximal independent sets of \((k+1)\)-valent trees |
scientific article |
Statements
The number of maximal independent sets of \((k+1)\)-valent trees (English)
0 references
22 September 2006
0 references
The authors derive recurrence relations for the number of maximal independent sets of nodes in planted plane trees in which each node has degree one or \(k+1\). The results can readily be deduced from a special case of results by \textit{A. Meir} and \textit{J. W. Moon} [J. Graph Theory 12, No. 2, 265--283 (1988: Zbl 0655.05039)] who enumerated maximal independent sets in simply generated families of trees and, in addition, obtained asymptotic results on the number and the expected size of these sets.
0 references
