Study On Distance Spectrum Of Kinds Of Graphs

The theory of graph spectrum mainly studies graph topological structure through adjacency matrix,Laplacian matrix,distance matrix and other related matrices and their eigenvalues and eigenvectors.It is widely used in chemistry,physics,computer information science,complex system and other fields,and is a very important research field in graph theory.The distance d_G（v_i,v_j）between two vertices v_i and v_j of a connected graph G is defined as the number of edges contained in a shortest path connecting vertices v_i and v_j.The distance matrix of graph G is denoted as D（G）=(d_ij)_n×n,and its rows and columns are indexed by the vertices of G,where d_ij=dG（v_i,v_j）.The distance spectrum of graph G refers to all eigenvalues of its distance matrix D（G）,and the largest eigenvalue is called the distance spectral radius of graph G.In this paper,we focus on a kind of popular problems in graph theory:the extremal graph characterization of distance spectrum of graphs.The main work is as follows:In Chapter 1,we first introduce some basic concepts and terms in graph theory,then introduce the research background and progress of distance spectrum,and finally give the main research results of this paper.In Chapter 2,we study the extremal graphs regarding to distance spectral radius of planar polyomino chains.By introducing the graph transformation and combining the knowledge of algebraic graph theory,we find the variation law of the distance spectrum of polyomino chains,and prove that the the linear polyomino chain L_n has the maximum distance spectral radius,the zig-zag polyomino chain Z_n has the minimum distance spectral radius among all planar polyomino chains containing n squares.In Chapter 3,we study the extremal graphs regarding to distance spectral radius of pentagonal chains.By introducing the graph transformation of pentagonal chains and using a similar method to chapter 2,we prove that among all pentagonal chains containing n regular pentagons,the first kind of pentagonal chain T_n¹ has the minimum distance spectral radius and the second kind of pentagonal chain T_n² has the maximum distance spectral radius.In Chapter 4,we consider the extremal graphs regarding to distance spectral radius of uniform hypertree T（m,d）with diameter d.By edge transformation,We proved that when the diameter d is even,the extremal graphs with minimum distance spectral radius is the uniform hypertree T_d/2（m-d）whose pendent edges outside the diameter path are all hanging at the center vertex v_d/2.When the diameter d is odd,the extremal graphs with minimum distance spectral radius is the uniform hypertree T_（d+1）/2（m-d）in the base tree T’（m,d）of T（m,d）.