On maximal independent sets of nodes in trees
- 1 June 1988
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 12 (2) , 265-283
- https://doi.org/10.1002/jgt.3190120217
Abstract
A subset / of the nodes of a graph is a maximal independent set if no two nodes of / are joined to each other and every node not in / is joined to at least one node in /. We investigate the behavior of the average numbere(n) and the average size μ(n) of maximal independent sets in treesTnwhere the averages are over all treesTnbelonging to certain families of rooted trees. We find, under certain conditions, thate(n) ∼q·Enand μ(n) ∼Snasn→ ∞, whereq,E, andSare constants that depend on the family being considered.Keywords
This publication has 11 references indexed in Scilit:
- The Number of Maximal Independent Sets in a TreeSIAM Journal on Algebraic Discrete Methods, 1986
- Fibonacci Numbers of Graphs III: Planted Plane TreesPublished by Springer Nature ,1986
- Fibonacci Numbers of Graphs: IIThe Fibonacci Quarterly, 1983
- Fibonacci Numbers of GraphsThe Fibonacci Quarterly, 1982
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978
- Packing and covering constants for certain families of trees. IJournal of Graph Theory, 1977
- Packing and covering constants for certain families of trees. IITransactions of the American Mathematical Society, 1977
- Asymptotic Methods in EnumerationSIAM Review, 1974
- The Multiplicative ProcessThe Annals of Mathematical Statistics, 1949
- Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische VerbindungenActa Mathematica, 1937