图谱及其在网络中的应用

图的谱是图的同构不变量，在图论研究中最关心的问题是图的谱与图的结构之间的关系。已有的研究结果表明，许多图类的结构可以由图谱完全确定，图的谱与图的许多重要结构参数密切相关，如直径、连通度、独立数、色数、亏格、等周数、带宽等等，利用它们可以给出这些结构参数简洁漂亮的界。图谱理论是代数图论的重要组成部分，而且被广泛应用于组合优化、网络及理论化学等领域。本项目将重点研究图的谱（包括图的邻接矩阵的最大特征值、图的Laplacian矩阵的最大特征值、第二小特征值和图的无符号Laplacian矩阵的最大特征值等）与度量网络性能的参数（例如，直径、（边）连通度、限制（边）连通度等）之间的关系及相关的极值问题。

按照计划，我们对项目所列的研究内容进行了深入的研究，并已取得了部分结果和进展。在SCIE检索杂志上正式发表论文2篇，在国家核心期刊上发表论文1篇，另有1篇论文已投稿。依托本项目，招收硕士研究生5名，其中2人已毕业。.本项目已取得的结果和进展如下：. 一、对谱半径进行估界。. （1）利用度序列，分别给出了赋权图的邻接谱半径和拉普拉斯谱半径的一个新的下界。根据这个下界可以推出非赋权图若干已知的下界。（2）确定了不含子图Bk+1和K2,l+1的图的无号拉普拉斯谱半径的上界。利用这个结果可以确定不含4圈的图以及围长至少是5的图的无号拉普拉斯谱半径的上界。. 二、刻画给定图类中具有最小谱半径的图。. 确定给定图类中具有最大或最小谱半径的图是图谱理论研究的一个重要方向，其中确定具有最小谱半径的图相对于确定具有最大谱半径的图而言更困难一些。我们按照邻接谱半径对树进行排序，在前人的基础上，进一步确定了谱半径第八、第九、第十小的树。. 三、刻画了秩为4的符号图的结构和秩为7的（符号）双圈图的结构。. 图的秩指的是图的邻接矩阵特征值中非零特征值得个数。简单图的秩与图的匹配数密切相关。近年来对图的秩的研究比较热。我们刻画了秩为4的符号图的结构和秩为7的（符号）双圈图的结构。在研究符号图的秩的基础上，我们进一步研究赋权图的秩。我们刻画了秩为2的赋权图和不含4阶完全图且秩为3赋权图的结构，并且将简单图秩的一些结论推广到了赋权图上。. 四、刻画给定图类具有较小的关联能量的图的结构。. 图的关联能量指的是图的关联矩阵的奇异值的和。对二部图而言，图的关联能量等于图的Laplacian矩阵的特征值的平方根的和。以前，图谱理论的研究主要集中在图的某个特征值。近年来一些涉及到多个特征值的参数逐渐受到更多的关注，比如各种定义的图的能量。在前人的基础上，我们进一步确定了具有第五——第七小的关联能量的树的结构。目前我们正在研究其他图类的关联能量的极值和极图，例如给定直径的树的关联能量。