Premium
On maximal independent sets of nodes in trees
Author(s) -
Meir A.,
Moon J. W.
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120217
Subject(s) - mathematics , combinatorics , graph , node (physics) , tree (set theory) , set (abstract data type) , independent set , discrete mathematics , computer science , structural engineering , engineering , programming language
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.