On Two Types Of Polynomials About Some Graphs

Graph polynomial theory is an important part of graph theory,and graph poly-nomial theory is a general term for various algebraic invariants of graphs.The main contents include characteristic polynomial,domination polynomial,color polynomial,matching polynomial and so on.We usually use characteristic polynomial to study the maximum and minimum eigenvalues of matrices,and obtain some important con-clusions related to graph by the coefficients of graph polynomials.And in this paper,we mainly study the characteristic polynomial and the total domination polynomial of graph G.In Chapter 3,we get some results about the total domination polynomials of graph G.Given a graph G,a total dominating set Dt of G is a vertex set that every vertex of G is adjacent to at least one vertex of Dt.Let dt(G,i)be the number of all total dominating sets of G with size i.The total domination polynomial of G is Dt{G,x)=(?)dt(G,i)xi.We obtain the vertex-reduction and edge-reduction formulas for total domination polynomials.As consequences,we give the total dom-ination polynomials for paths.Then we determine a consistent upper bound,that is((?)),for all coefficients of total domination polynomials for trees and characterize the corresponding graph that attains such bounds is the star Sn.Additionally,we investigate the values of total domination polynomials of some graphs at x=-1.In Chapter 4,we show some results about the characteristic polynomials of graph Gn,d*.In order to study the properties of spectrum,V.Nikiforov presented the A?-matrix:A?(G)=?D(G)+(1-?)A(G),? ?[0,1],where D(G)is the degree matrix and A(G)is the adjacency matrix of G.The introduction of this new concept undoubtedly draw attention,and many researchers actively study related properties.Let B(n,d)be the family of graph G with given diameter d and order n.In this part,we show the structure of Gn,d*that attains the maximum A?-spectral radius in B(n,d),and then we obtain the characteristic polynomials of A?-(Gn,d*)-matrices.