On maximal independent sets of nodes in trees | Zendy

Meir A. | Zendy; Moon J. W. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research