Counting The Matchings, Independent Sets And Maximal Independent Sets For Several Classes Of Graphs

This paper which stands on the basis of previous results, and which further research on the issue of the number of independent sets, matching sets and maximal independent sets for several graphs, mainly includes:(1)On the first and second sections, we introduce the paper's research background and significance, including the development of a representative at home and abroad regarding this aspect. Based on this research background and profound discussion on the status quo, it fully shows the main work's necessity and innovation.(2)On the third section, we determine upper and lower bounds for the number of independent sets in a bicyclic graph in terms of its order, we determine upper bound for the total number of independent sets in a connected graph which contains at least two cycles. In each case,we characterize the extremal graphs;(3)On the fourth section, we determine the largest, the second-largest, the smallest and the second- smallest number of independent sets in quasi-tree graphs for order n, Then we characterize the n-vertex quasi-tree graphs with the largest, the second-largest, the smallest and the second-smallest number of match stes, as well as those n-vertex quasi-tree graphs with k pendent vertices having the smallest number of match sets, the extremal graphs are also characterized.(4) On the fifth section, we determine the largest number of maximal independent sets among all connected graphs on n vertices with cyclomatic numberη, forη≤2. We also characterize those extremal graphs achieving the maximum values;(5)On last section, Established on the following article G.C. Ying, K.K. Meng, B. E. Sagan, and V.R. Vatter[Maximal independent sets in graphs with at most r cycles, J. Graph Theory, 53(2006), 270-282], we determine the second largest number of maximal independent sets for the graph with at most r cycles, the extremal graphs are also characterized.