The Number Of Maximal Independent Sets In Trees

Erdos and Moon raised the question of determining the maximal independent sets in graphs. This problem has been solved by Moon and all the extremal graphs achiev-ing the maximum value were determined. The number of maximal independent sets in graphs is of tremendously theoretical significance, and plays important roles in im-proving and designing algorithms for problems in graph theory. In the last decades, many researchers have made intensive study on this problem. Recently, researchers fo-cus on the number of maximal independent sets in graphs with additional constrained conditions.In this thesis, we focus on the number of maximal independent sets in trees. Our work mainly includes three parts:(1) In the third section, we study the number of maximal independent sets in trees with large maximum degree. We determine the maximum values and characterize the extremal graphs of the corresponding trees.(2) In the fourth section, we study the maximal independent sets in trees without including any leaves. In particular, we determine some small and the largest number of these sets. Extremal trees achieving these values are also determined;(3) In the fifth section, we determine the fourth and fifth largest number of max-imal independent sets in trees. Extremal trees achieving these values are also deter-mined.