特征值与图的结构

Spectral graph theory is the study of the eigenvalues of the.algebraic representations (i.e. matrices corresponding to graphs)of graphs. By investigating the eigenspace of graphs, set up the relation between eigenvalues and topological structure of graphs.Use algebraic theory, geometric theory and probabilistic method to study the structure properties of graphs and apply graph theory to study the spectral problem in algebra and geometry..The project is devoted to the following problems which have attracted much attention of international spectral researchers, including the normalized Laplacian and distance matrix of graphs, the nullity of graphs and their applications in chemistry. We shall study the second smallest eigenvalue and spectral radius of the normalized Laplacian and find the relation between them and various invariants of graphs. Meantime, we shall study the spectral perturbation on the second smallest eigenvalue and spectral radius of the normalized Laplacian of graphs, perhaps from which we can characterize the graphs with extremal value of the second smallest eigenvalue and spectral radius of the normalized Laplacian among various classes of graphs. Try to extract the information of the graph structure from the harmonic eigenfunction corresponding to the second smallest eigenvalue of the normalized Laplacian. We shall investigate the problem of classifying all bipartite graphs according to their rank or nullity. Characterize the nullity of some fundamental graphs. We shall study the spectral radius and determinant of distance matrix of graphs.

谱图理论主要研究图的代数表示（图对应的矩阵）的谱，通过讨论图的特征空间，建立图的拓扑结构与图的特征值之间的联系，应用代数理论、几何理论与概率方法来研究图的拓扑结构性质，以及应用图的拓扑结构来研究代数和几何中的谱性质。.本项目主要研究谱图理论中国际上重点关注的几个问题，包括图的规范化Laplacian与距离矩阵、图的零度及其在化学的应用。研究图的规范化Laplacian的次小特征值与谱半径，建立其与图的各种不变量之间的联系。研究图的规范化Laplacian的次小特征值与谱半径的谱扰动，由此给出各种图类中具有极端规范化Laplacian次小特征值与谱半径的极图刻画。研究规范化Laplacian次小特征值对应的调和特征函数所反映的图的组合结构性质。探索依秩或零度对二部图的分类问题，给出基本图类的零度刻画。研究图的距离矩阵的谱半径与行列式。

本项目研究了图和超图的谱以及图的匹配理论，发表（含录用）了16篇学术论文。研究了图的规范化拉普拉斯谱与图的结构的关系，给出了规范化拉普拉斯次小特征值的较优的下界。刻画了几类图的关于距离矩阵谱半径的极图，研究了加权图的q-距离矩阵的行列式。确定了秩为2和3的带号图和秩为4的二部带号图。由于超图的广义性及其在其它学科的重要应用，我们研究了超图的特征值，特别是超图的邻接张量、无号拉普拉斯张量和关联Q-张量的谱半径，通过引入的超图的几种变换及超树（无圈连通超图）关于这些变换的谱半径的扰动情况，刻画了具有（关于这三种张量的）最大和第二大谱半径的超树，同时确定了具有最小谱半径的hypertree（一类重要的特殊的超树）。我们给出了（有限或无限）正则超图的谱半径的一个下界，特别是我们成功地将Alon-Boppana定理推广到了超图上。这为进一步研究超图的扩容性质提供了基础。我们解决了单圈图的无号拉普拉斯系数的极值问题，给出了具有最大和最小无号拉普拉斯系数的极图刻画。我们的结论实际上也能够解决带号图的拉普拉斯系数极值问题，这由15年LAA的一篇文章的作者所指出，此外我们的结论还为研究图的匹配数提供了方法，项目实施过程中有关图的匹配数的很多结果由此开端。由图的匹配数序列确定的图上的拟序在上个世纪70年代引入，与图的匹配多项式和匹配能量以及Hosoya指数等概念关系密切。我们研究了一些图类关于此拟序的最大元和最小元，包括单圈图和双圈图，以及给定围长的单圈图和双圈图。特别是给出了图的几个重要的变换，能够使匹配数单调增大或较小，由此通过图在这些变换下匹配数的扰动情况，确定了几类图关于此拟序的极图，以及图的补图关于此拟序的极图刻画。