The Number Of Maximal Independent Sets In Graphs With Constraints

In 1960, Erdos and Moser raised the problem of determining the maximum num-ber of the maximal independent sets for a general graph G of order n and the time of those graphs achieving this maximum value. This problem was solved by Erdos, and later by Moon and Moser. In the past decades, the problem has been extensively stud-ied for various special classes of graphs. Today the main direction is to determine the number of maximal independent sets of graphs under some restrictive conditions.On the basis of previous works, this thesis studies the problem of the maximal independent sets in graphs under some restrictive conditions. The main results of this dissertation may be summarized as follows:(1) In the study of counting the number of the maximal independent sets in trees, it has been proved that the corresponding extremal trees always have just one vertex with maximum degree. In this paper we consider the problem of determining the largest number of maximal independent sets for trees with two maximum degree vertices. Extremal trees achieving these values are also determined;(2) It has been proved that the extremal trees with the largest (second, third) number of maximal independent sets always have a small diameter. In this paper we study the problem of the largest number of the maximal independent sets for trees with a large diameter. Extremal trees achieving these values are also determined;(3) At last, we study the problem of counting the number of the maximal inde-pendent sets in the line graph of unicyclic graph. We characterize the structure of the line graph of unicyclic graph with the largest number of the maximal independent sets.