The Laplacian Spectrum And Distance Spectrum Of Some Graphs

The spectral graph theory is one of the important fields of graph theory and combinatorial matrix theory,which mainly concerned with the spectrum,Laplacian spectrum and distance spectrum of a graph and is used widely in quantum chemistry, physics,Computer science,communication networks and information science and so on.In this thesis,we consider the extremal graphs about Laplacian spectral radius of bipartite graphs with k cut edges,bicyclic bipartite graphs,unicyclic graphs with fixed diameters,unicyclic graphs with k pendent edges;some graphs determined by their spectra;cospectral graphs;minimal distance spectral radius.There are five chapters altogether in the thesis.In the first chapter,besides introducing the background of the Laplacian spectral graph theory,some concepts and notations,we mainly present the research problems and their developments,and introduce the main results obtained in the following chapters.In chapter 2,we discuss the extremal graphs(about Laplacian spectral radius) of bipartite graphs.Among all the the bipartite graphs with n vertices and k cut edges, and among all the bicyclic bipartite graphs,the largest Laplacian spectral radius is uniquely obtained at K_2,n-k-2^k,K_2,3^n-5(n≥7),respectively,where K_m,n^k is obtained by identifying the center of a star K_1,k and one vertex of degree n of K_m,n,k,m,n are all integers.In chapter 3,we get a formula for the Laplacian characteristic polynomial of graphs with cut vertices.As applications,we prove that,among all the unicyclic graphs with n vertices and fixed diameter d(3≤d≤n-3),and among all the unicyclic graphs with n vertices and k(k≤n-4) pendent edges,the largest Laplacian spectral radius is uniquely obtained atâ—‡_n^d,â–¡₄^k,respectively,whereâ—‡_n^d denotes the graph obtained from C₄=v₁v₂v₃v₄v₁ by attaching n-d-2 pendent edges together with a path of length[d/2]-1 to vertex v₁,and a path of length[d/2]-1 to vertex v₃,andâ–¡₄^k denotes the graph on n vertices obtained from C₄ by attaching k paths of almost equal lengths at the same vertex.In chapter 4,we discuss some graphs determined by their spectra.We first prove that the graph K_n^m and its complement are determined by their adjacency spectra,and by their Laplacian spectra.Then we prove that U_n,p is determined by its Laplacian spectrum,as well as its adjacency spectrum if p is odd,and find all its cospectral graphs for U_n,4,where K_n^m denotes the graph obtained by attaching m pendent edges to a vertex of complete graph K_n-m,and U_n,p the graph obtained by attaching n-p pendent edges to a vertex of C_p.At last,we find a class of graphs which not only have the same spectrum,Laplacian spectrum but also have the same distance spectum.In chapter 5,we mainly study the distance spectral radius.We first study how the distance spectral radius behaves when the graph is perturbed by grafting edges,then, as applications,we also prove that the minimal distance spectral radius is uniquely obtained at the graph G_n,k(respectively,K_n^k) among all the graphs with n vertices and k cut vertices(respectively,k cut edges),where G_n,k is a graph obtained by adding paths P_{l1+1,…,} P_ln-k+1 of almost equal lengths to the vertices of the complete graph K_n-k.