Research On The Independence Polynomials Of Graphs

Let G=(VG, EG) be a simple connected graph. A set of pairwise non-adjacent vertices in G consist of an independent set of G. Let ik= ik(G) be the number of independent sets of cardinality k of G. The independence polynomial I(G, x)= ∑k≥0ik(G)xk defined first by Gutman and Harary has caused extensive concern and research recently, whereas i(G)=i(G,1) is called Merrifield-Simmons index of G. The idea of counting independence sets in graphs seems to begin with a paper of Prodinger and Tichy, see [1]. For the coefficients of independence polynomial of graphs, we introduce a relation (?) to order graphs. The concrete content is in the following:● In Chapter 1, we introduce the background and significance of the research, including the development of a representative at home and abroad regarding this aspect. Based on this research background and profound discussion, by using deep-going analysis, it fully shows the main work’s necessity and innovation.● In Chapter 2, we give some necessary definition and related lemmas.● In Chapter 3, we characterize the graphs whose all coefficients of I(G, x) are largest or smallest with given graphic parameters, such as diameter, girth, chro-matic number, clique number, connectivity. By our results we may deduce some known results on Merrifield-Simmons index.● In Chapter 4, we summarize the main results of this thesis and give some prospects for further research in the future.