Adjoint Polynomials And Independent Set Polynomials Of Graphs

In recent years, the graph polynomials are studied more and more widely. This is because it set up a bridge between graph theory and traditional algebra. There are many kinds of polynomials, such as characteristic polynomial, adjoint polynomial, chromatic polynomial, matching polynomial and independence polynomial and so on. In this paper, we mainly study the adjoint polynomial and independence polyno-mial of graph. In the first part of this paper, we prove that factorization theorem of adjoint polynomials of a kind of graphs PnG U tG and ΦG(κ, n) U (2k+1)G, and thus obtain chromatic equivalence of their complements. In the second part of this paper, we first prove that some compound graphs are independence equivalent. Then we discuss the independence polynomials of some compound graphs and thus using the independence polynomials we derive some interesting combinatorial identities and give exact values of the Merrifield-Simmons index for some special classes of graphs.The construction of chapters and the concrete contents of this paper are as follows:Chapter1:Preliminaries. We give the basic concepts of adjoint polynomial, adjoint equivalent, independence polynomial and independence equivalent and so on which will be used in this paper.Chapter2:Adjoint polynomial. At first, we prove that factorization theorem of adjoint polynomials of a kind of graphs. Then, we obtain chromatic equivalence of their complements.Chapter3:Independence polynomial. Firstly, we prove that some compound graphs are independence equivalent. Then, using the independence polynomials we derive some interesting combinatorial identities and give exact values of the Merrifield-Simmons index for some special classes of graphs.