Some Properties Of Independence Polynomials Of Graphs

Algebraic graph theory is the field of using algebraic methods to study the problems in graph theory.Especially,the study of the unimodality of independence polynomials of graphs is a key topic in algebraic graph theory.In 1987,Erd ?os et al.conjectured that the independence polynomial of any tree or forest is unimodal.However,this conjecture has not been completely solved so far,and it was only established for some special classes of graph.In this dissertation,using the rooted products of graphs,we will prove that some new families of graphs preserve real-rootedness of independence polynomials,and their independence polynomials are therefore unimodal.This further verifies this conjecture.In addition,the Christoffel-Darboux type identities of the orthogonal polynomials are closely related to the graph polynomials.It has been found that both the matching polynomials and the independence polynomials have such properties.In this dissertation,we will also use the multiple-affine independence polynomials to extend some Christoffel-Darboux type identities of univariate independence polynomials to multivariate.The details are as follows:In Chapter 1,we introduce the research background,the basic definition of the graphs involved in this dissertation,and the unimodality of polynomial.In Chapter 2,using the rooted products of graphs,we will prove that some new families of graphs preserve real-rootedness of independence polynomials,and their independence polynomials are therefore unimodal.As applications of our results,some known results are generalized.In Chapter 3,using the multiple-affine independence polynomials,we extend some Christoffel-Darboux type identities of univariate independence polynomials to multiple-affine independence polynomials.In Chapter 4,conclusion.