特征值、子图存在性及图的结构参数

图谱理论主要通过研究图的相关矩阵来反映图的结构特征，是图论与矩阵论的交叉领域。图的特征值一方面可以作为研究图的结构性质（如哈密尔顿圈的存在性，完全子图的存在性，完全二部子图的存在性，生成树的个数等）的重要工具；另一方面，图的特征值与图的一些结构参数之间的联系也有着广泛的应用背景。2003年，Wang等人提出了网络病毒传播模型, 网络的最大特征值越小，其抵御病毒攻击能力就越高。因此，在保证网络传播性能的前提下，减小其最大特征值是网络设计的重要课题。近来，我们开展了以下两方面的研究：一，图的特征值与图的某种子图（如完全子图，完全二部子图，给定长的路，圈等）的存在性之间的联系。二，图的特征值与图的各种结构参数（如团数，直径，独立数，围长等）之间的关系。项目组希望通过本项目的研究，探索图的矩阵性质与图的结构性质之间的内在联系，并在研究过程中挖掘和丰富图谱理论的研究工具，以期推动一些问题的解决。

本项目研究内容和成果主要包括以下两个方面： 一、图的邻接特征值的定界和极图刻画问题。该问题是图谱理论中的经典问题，关于谱半径、最小特征值、第二大特征值等在过去几十年中有一系列重要的结果。其中，关于图的第二大特征值，A. Neumaier（1982年）和邵嘉裕教授（1995年）分别给出了奇数阶和偶数阶的树的第二大特征值的上界并刻画了极图；Powers（1988年）和洪渊教授（1988年）则研究了二部图和一般图的第二大特征值的上界。而在二部图和一般图上第二大特征值可达的上界和极图目前没有得到充分的考虑。近来，我们将谱方法与结构图论方法相结合，利用特征分量结合图的划分的方法，将树上的结果推广到了连通二部图和连通一般图上，给出了第二大特征值的可达上界，并刻画了不同情况下所有的极图类。.二、子图存在性与图的特征值问题。 该问题是近期图谱理论研究的热点问题，该问题很好的体现了谱方法在结构图论研究中的价值。极值图论中的经典问题之一是：对给定的图H，一个n阶的H-free 图的最大边数是多少？著名的图兰定理回答了H为团时的结果。在过去几十年中，很多学者开始关注上述问题的谱版本，即：对给定的图H，一个n阶的H-free 图的最大谱半径是多少？众所周知，若H是星图K_{1,r+1}，则极图是r-正则图。近年来，Fiedler 和Nikiforov（2010年）解决了H是生成圈和生成路的情形，Nikiforov解决了H是奇圈的情形（充分大n，2008年）及H是完全图K_{r+1}或完全二部图K_{2,r+1}情形（r\geq2,2007年）。2009年，Nikiforov 获得了H是C_4-free 图的谱半径上界，并得到极图是 friendship graph (此时，n 是奇数)。他猜想若n 是偶数，则极图是由 friendship graph加一条悬挂边到其中心点所得的图。我们证明了这一猜想,从而C_4-free 图的谱极值问题完全解决. 2010年，Nikiforov 获得了H\cong P_{2k+2}或H\cong P_{2k+3}时的极图，并提出H\cong C_{2k+2}（k\geq2）时的一个猜想，近来，我们解决了H\cong C_6（即k=2）的情形，后又在二部图中解决了H是P_{2k+2}、P_{2k+3}、C_{2k+2}的问题。