Research On The Characteristic Polynomial Coefficients Of Graphs

Let G be a simple graph with n vertices and m edges.L(G)be the Laplacian matrix of G.The Laplacian characteristic polynomial P(G;x)of G is defined as where ci(G)is referred as the i-th Laplacian coefficient of G.Denote Gn,m by the set of all connected(n,m)-graphs.A connected graph H?Gn,m is called ci-minimal if ci(H)?ci(G)holds for each G ? Gn,m and is called laplacian uniformly minimal if H ? Gn,m is ci-minimal for i=0,1,…,n.In the first part of this dissertation,we will discuss the minimization of Laplacian coefficients of graphs and the existence of uniformly minimal graphs and prove that each ci-minimal graph in Gn,mis a threshold graph for 2?i?n-2.Moreover,we prove that there does not exist uniformly minimal graphs in Gn,n+3(n?6).Q(G)is the Signless Laplacian matrix.The Laplacian characteristic polynomial Q(G;x)of G is defined as where bi(G)is referred as the i-th Laplacian coefficient of G.We call that connected graphs H?Gn,m are bi-minimal if bi(H)?bi(G)holds for each G?Gn,m and is called signless laplacian uniformly minimal if H?Gn,m is bi-minimal for i=0,1,…,n.In the second part of this paper,the structure of uniformly minimum graphs of tricyclic graphs is given.We first give three kinds of graphs which can make the signless Laplace coefficients of graphs uniformly smaller.The structure of the uniform graph of signless Laplace coefficients of tricyclic is studied.We corrected the wrong result of Lu Hongyan[Reaech on The signless Laplacian coefficients and incidence energy of tricyclic graphs].Lu Yanhong calculated and compared the structure of the tricyclic graph and the minimum graph among 60 candidate graphs.By using the above three graph transformation,we reduce the candidate graph range to 7,which simplifies the difficulty of the problem.