Researches On The Eigenvalues And Structural Parameters Of Graphs

The theory of graph spectra is one of important areas in graph theory and is extensively applied to computer science,information science,commu-nication network,quantum chemistry,statistical mechanics and other fields The study of the theory of graph spectra aims to establish the close relation-s between the algebraic properties and the topological structure of graphs through the matrix representation of graphs and with classical conclusions and techniques in the matrix theory and combinatorial matrix theory.In this paper,we mainly study the relations between the eigenvalues of several matrices and some structural parameters of graphs(such as degrees,average 2-degree,transmission,diameter,girth,chromatic number,connectivity of graphs and so on)so as to study the properties of graphs.The thesis is organized as followsIn Chapter 1,we mainly give some backgrounds of the theory of graph spectra and the related questions we study in this thesis.Moreover,some basic concepts and notations used in our research are introducedIn Chapter 2,we study the(signless)Laplacian spectral radius of non-regular and connected(n,m)-graphs(i.e.,the graphs with n vertices and m edges).Firstly,we give an upper bound on the signless Laplacian spectral radius of graphs with degree and average 2-degree and characterize the ex-tremal graphs.Secondly,an upper bound for the(signless)Laplacian spectral radius of graphs with the maximum and minimum degrees is given.Thirdly,we discuss the relations between the Laplacian spectral radius of graph G and the signless Laplacian spectral radius of graph G'(? G).In addition,we give the comparison and ordering of the(signless)Laplacian spectral radii of different graphs.In Chapter 3,we investigate the least eigenvalue ?n(Aa)of Aa-mattrix of graphs.Let n,m,? and qn(G)respectively denote the order,size,chromatic number and the least eigenvalue of the signless Laplacian of graph G.de Li-ma,Oliveira,de Abreu and Nikiforov[The smallest eigenvalue of the signless Laplacian,Linear Algebra Appl.435(2011)2570-2584]proposed some open problems on qn(G),two of which are as follows:Problem 1:Find the necessary and sufficient conditions of equality qn(G)= 2m/n-1.Problem 2:Find the necessary and sufficient conditions of equalityIn this chapter,we firstly present an upper bound on ?n(A?)(where 1/2??? 1)and characterize the extremal graphs.As an application,we com-pletely solve Problem 1.Moreover,when ??1/?,we find some necessary conditions for the equality ?n(A?)=(??-1)2m/(?-1)n in the upper bound given by Nikiforov and Rojo[A note on the positive semidefiniteness of Aa(G)Linear Algebra Appl.519(2017)156-163]and then obtain some necessary condi-tions for the equality in Problem 2.Finally,we give some bounds on ?n(A?)in respect to degrees,diameter and girth of graphs and characterize some ex-tremal graphs,and some of these obtained results can improve and generalize some known results on qn(G)and ?n(A?).In Chapter 4,we consider the distance(signless Laplacian)spectral ra-dius of graphs.In one section we study the distance spectral radii and for-warding indices of circulant graphs.Firstly,we construct the short paths between any two vertices of several classes of circulant graphs and then give the distance spectral radii and all entries of the corresponding distance matri-ces.In addition,we get the relations between the distance spectral radii and forwarding indices of circulant graphs.Finally,the exact values of the vertex forwarding indices and some lower and upper bounds on the edge forwarding indices for these kinds of graphs are presented.In another section we study the the distance(signless Laplacian)spectral radius and(twice)the maxi-mum transmission of non-transmission-regular graphs.We respectively esti-mate the difference between the distance(signless Laplacian)spectral radius and(twice)the maximum transmission of non-transmission-regular graphs and compare these obtained results.Moreover,we give a conjecture on the distance spectral radius and the maximum transmission of non-transmission-regular graphs and confirm that the conjecture is true for trees.In addition,using the similar method given in the proof we improve one known result on the difference between the adjacency spectral radius and the maximum degree of graphs.In Chapter 5,the whole paper is summarized and some problems for further research are discussed.