On maximal independent sets of nodes in trees

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 number e ( n ) and the average size μ( n ) of maximal independent sets in trees T n where the averages are over all trees T n belonging to certain families of rooted trees. We find, under certain conditions, that e ( n ) ∼ q · E n and μ( n ) ∼ Sn as n → ∞, where q , E , and S are constants that depend on the family being considered.