Structure Variables And Eigenvalues Of Graphs

The theory of graph spectra is an active and important area in graph theory. There are extensive applications in the fields of quantum chemistry, statistical mechanics, computer science, communication networks and infor-mation science. In the theory of graph spectra, there are various matrices that are naturally associated with a graph, such as the adjacency matrix, the Laplacian matrix, the incidence matrix, the distance matrix and so on. One of the main problems of graph spectra theory is to determine precisely how, or whether, properties of graphs are reflected in the algebraic proper-ties (especially properties about eigenvalues, such as spectral radius, spectral uniqueness, spread, energy and so on) of such matrices.Among the above mentioned matrices of graphs, the most important two are the adjacency matrices and the Laplacian matrices of graphs. This thesis mainly investigates the spectral radii and the spreads for adjacency matrices and Laplacian matrices of graphs and tries to build some connections between them and some structure variables of corresponding graphs. The main content of this thesis are as follows.(1) In Chapter 1, we first look back the evolvement of graph theory. And then introduce the backgrounds and research progresses of some questions on graph spectra theory that we study. At last, some definitions and notations for the corresponding questions are introduced.(2) In Chapter 2, we study the connections between the adjacency spec-tral radii and some structure variables of graphs. In [119], E.R. van Dam characterized the extremal graph with maxiaml adjacency spectral radius among all connected graphs with given diameter. Here, the extremal graph with maximal adjacency spectral radius is determined among all bipartite graphs with given diameter. Also the extremal graph is determined for the class of bicyclic graphs with given girth.(3) In Chapter 3, we investigate the connections between the Laplacian spectral radii and some structure variables of graphs. We first give an edge-grafting theorem on Laplacian spectral radius, by which the unique graph with maximal Laplacian spectral radius is determined among all bicyclic graphs with given girth. Moreover, we obtain an upper bound of Lapla-cian spectral radius according to diameter and characterize the graphs with maximal Laplacian spectral radius among all graphs with given diameter.(4) In Chapter 4, we investigate the problem about the spread of graphs. The adjacency spectral spread means the difference between the spectral radius and the least eigenvalue of the adjacency matrix. And the Laplacian spectral spread is defined to be the difference between the Laplacian spectral radius and the algebraic connectivity. We first study the adjacency spectral spread and corresponding extremal graph for the class of oo-bicyclic graphs, and then investigate the Laplacian spread of general graphs.(5) In Chapter 5, we investigate the connections between the distance spectral radii and clique number of graphs. Among all connected graphs with given clique number, the extremal graphs with maximal and minimal distance spectral radii are respectively determined.