Study On Eigenvalue-related Problems Of Three Classes Of Graphs

The study on the eigen-roots of graphs and hypergraphs is one of hot topics in the graph theory.The roots of the matching polynomials of graphs,the spectral radii of r-uniform linear supertrees and the energy of signed graph are the three important problems in the studying of graph theory.Investigation on these three problems is of great theoretical significance for the in-depth insight into the structure and properties of graphs and hypergraphs.Let G be a simple connected graph of order n.The matching polynomial of G is given by MG(x)??k=0[n/2](-1)km(G,x)xn-2k,where m(G,k)is the number of k-matchings of G with 0?k?[n/2].The roots of MG(x)=0 is called the roots of the matching polynomials of G.Let H be an r-uniform supertree.The matching polynomial of H is defined as ?(H,x)??k=0v(H)(-1)km(H,k)x(v(H)-k)r where m(H,k)is the number of k-matchings of H and v(H)is the maximum cardinality of a matching of H.Let S be a simple connected signed graph with n vertices.The energy of S is defined as ?(S)??i=1n?|?i|,where ?i is the eigenvalue of the characteristic polynomial of S.The main results of this thesis consist of three parts.1)The largest root of the matching polynomials of ?n,m is studied,where ?n,m is the set of graphs with n vertices and m edges having no even cycles with n?m?3(n-1)/2.Four new transformations for comparing the largest roots of matching polynomials are introduced and the graph with the largest root of matching polynomial is characterized among ?n,m.2)The supertrees with the extremal spectral radii among several kinds of r-uniform supertrees are investigated.Firstly,by using the matching polynomials of su-pertrees,two new and useful grafting operations are proposed for comparing the spectral radii of supertrees,and their applications are shown to obtain the supertrees with the extremal spectral radii among some kinds of r-uniform su-pertrees.Secondly,the supertree with the third smallest spectral radius among the r-uniform supertrees is deduced.Thirdly,among the r-uniform supertrees with a given maximum degree,the supertree with the smallest spectral radius is derived.At last,among the r-uniform starlike supertrees,the supertrees with the smallest and the largest spectral radii are characterized.3)The increasing order of the signed graphs among U2n? is considered according to their minimal energies,where U2n? is the set of unicyclic signed graphs with perfect matchings having 2n vertices with ? is a signing function.A relationship between the energies of a unicyclic graph and of its signed graphs is derived.A new integral formula for comparing the energies of two signed graph is introduced.In U2n? with n? 721,the first 18 signed graphs in the increasing order by their minimal energies are obtained.