The number of maximal independent sets of \((k+1)\)-valent trees (Q2504102): Difference between revisions

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.