图的矩阵特征值研究

【作者】 王志文；

【导师】 郭继明；

【作者基本信息】 华东理工大学 ， 应用数学， 2020， 博士

【摘要】 图谱理论已广泛应用于数学、化学、物理和计算科学等多个科学领域。图谱理论研究基于图的矩阵的相关性质进行分析讨论,将图的性质转化为代数性质,并导出关于图的理论。本文将重点考虑图的邻接矩阵,以及无符号拉普拉斯矩阵、规范拉普拉斯矩阵和Aα-矩阵,其大致内容分布如下:(一)考虑了邻接矩阵的谱半径。利用矩阵拆分,得到去点的诱导子图与原图谱半径的关系。并推导出谱半径只与点数和边数相关的一个新的上界,而且该上界较之谱半径已知的一个只与点数和边数相关的上界更好。还讨论了两种图运算对谱半径的影响,获得了两个图粘合后的谱半径的上界,其推广了 Passbani和Salemi的一些结果,以及获得了收缩内部边对谱半径的影响,其推广了 Hoffman和Smith的一个结果。(二)讨论了邻接矩阵零特征值的重数。利用星补的方法完全证明了 Zhou、Wong和Sun提出的一个连通图中零度关于点数和最大度的猜想。对于点数n和直径d,刻画了零度η满足η=n-d或者η=n-d-1的所有的树。进一步,刻画了满足η=n-d的所有的极图。此过程中,还证明了毛毛虫图是极小图的充分必要条件。(三)讨论了邻接矩阵的第二小和第三小特征值。首先考虑到连通图与其连通子图之间的结构关系,再利用Cauchy交错定理证明了第二小特征值达到前四大的图。利用Torgasev关于只包含两个负特征值的基本图的结果,证明了第三小特征值达到最大值的所有图。(四)讨论了无符号拉普拉斯矩阵和规范拉普拉斯矩阵。利用无符号拉普拉斯矩阵最小特征值对应的特征向量与图的结构的关系,在某类单圈图中,我们确定了唯一使得图的最小的无符号拉普拉斯特征值达到最小的图,相应地,使得无符号拉普拉斯谱展达到最大的图也得到了刻画。通过矩阵张量积的计算,得到了加边对图的规范拉普拉斯特征值的影响,从而得到了在聚类中加边对图的规范拉普拉斯特征值的影响,并证明在聚类中加边将使其规范拉普拉斯能量严格增加的结论。(五)研究了Aα-矩阵。给出了任意图的Aα-矩阵的特征多项式与去点、去边和诱导子图后的Aα-矩阵的特征多项式的关系。结论推广了图的邻接矩阵去点和去边对应的结果以及推广了图的拉普拉斯矩阵去点、去边和去诱导子图对应的结果。证明了树T的第k大Aα特征值的上界,结论在一定程度上推广了 Shao和Guo分别关于邻接矩阵和拉普拉斯矩阵的结果。更多还原

【Abstract】 Some parts of the theory of graph spectra have been applied to many scientific ar-eas,such as mathematics,chemistry,physics and computer science.Researches on spectral graph theory are based on some properties of matrices of graphs.The methods translate properties of graphs into algebraic properties,by which we can deduce theorems about graphs.The priority of this thesis is adjacency matrix of a graph mentioned,as well as its signless Laplacian matrix,normalized Laplacian matrix and Aα-matrix.The general contents are as the following.(a)We consider the spectral radius of adjacency matrix of a graph.By splitting matrix,we get the relation between the spectral radius of a graph and that of its induced subgraph with deleting a vertex.And then a new upper bound only related to the numbers of vertices and edges are deduced,which is better than a known upper bound which is also related to the numbers of vertices and edges of a graph.We also study effects upon the spectral radius of two operations on graph.We obtain upper bounds on the spectral radius of the coalescence of two graphs,which generalize some results by Passbani and Salemi.And we get effects upon the spectral radius by contracting an internal edge,which generalizes a result by Hoffman and Simth.(b)We investigate the multiplicity of zero as an eigenvalue of adjacency matrix.By method of star complement,we completely solve a conjecture proposed by Zhou,Wong and Sun.And the conjecture is about the nullity related to the number of vertices and the maximum degree of a connected graph.For all trees with n vertices and diameter d,we characterize all trees with its nullity satisfying η=n-d or η=n-d-1.Furthermore,all graphs with η=n-d are also characterized.At the process of proof,we get the sufficiency and necessary condition that a caterpillar is minimal.(c)We investigate the second and the third least eigenvalues of adjacency matrix of a graph.Firstly,the structure relation between a connected graph and its connected sub-graphs is considered.Then we obtain the connected graphs with the first 4 largest second least eigenvalues by Cauchy inequality.Since Torgasev characterized canonical graphs with exactly two negative eigenvalues,we provide all graphs with the maximum third least eigen-value.(d)We investigate signless Laplacian matrix and normalized Laplacian matrix.We get information of the eigenvector corresponding the least signless Laplacian eigenvalue by considering the structure of a graph.In particular family of unicycle graphs,we characterize the graph minimizing the least signless Laplacian eigenvalue.Consequently,The graph with maximum signless Laplacian spread is determined.By computing tensor product of matrices,we investigate the effects of normalized Laplacian eigenvalues of a special class of graphs by adding edges.And then the effects of normalized Laplacian eigenvalues of a graph by adding edges into a cluster are obtained.We also prove that the normalized Laplacian energy will strictly increase when edges are added into a cluster.(e)We investigate Aα-matrix of a graph.For a graph G with vertex v,edge e and in-duced subgraph H,we display the relations between the characteristic polynomial of Aa(G)and the corresponding polynomials of Aα(G-v),Aα(G-e)or Aa(G-H).These results generalize the corresponding results of A(G)by deleting a vertex v or an edge e and of L(G)by deleting a vertex v,an edge e or an induced subgraph H.We also show an upper bound of the kth Aα eigenvalue of a tree,which in a sense generalizes results on adjacency matrix and Laplacian matrix by Shao and Guo respectively.更多还原