图的谱特征问题及其相关专题研究

图的谱理论一直是代数图论的主流研究方向。虽然其发展日臻成熟，但一些著名难题的解决至今进展甚微，其中之一就是图的谱特征问题。该问题不仅与图论中的两大难题（图的同构问题和图的重构猜想）密切相关，而且还被推广到群论、物理科学和Riemann几何中。基于此问题的Schwank猜想以及van Dam和Haemers猜想是完全对立的，但这个两个猜想仍无进展。本项目主要研究特殊图类、混合谱特征问题、同谱图、一般图和相关专题等五大方面。这一难题的研究具有重要的理论价值和应用价值，尤其在算法复杂性理论方面。项目有两方面的创新点：新的研究内容：包括图的Q-谱理论、推广Schwank的结论、非正则的广义线图、双变量特征多项式和Bartholdi-zeta-函数；新的研究方法：研究Q-谱所采用的异于其它谱的方法；研究非正则广义线图时找到新的切入口；引入图的Bartholdi-zeta-函数、特征空间和特征向量等。

项目主要研究图的谱特征及其相关专题，涉及图的邻接谱、Q-谱和Laplacian谱等，重点包括五个方面的研究内容：特殊图类、混合谱特征、同谱图、一般图和相关专题的研究。 主要成果如下：(1) 在特殊图类的研究上，找到了研究广义线图的A-谱特征问题的新方法，分别研究了广义鸡尾酒宴图、双星图和棒棒糖图的线图的A-谱特征问题，得到的结果部分地回答了E.R.van Dam和W.H.Haemers教授提出的问题；研究了多重锥图的A-谱特征问题，提出的关于友谊图A-谱特征的猜想引起了国外图论专家K.Ch. Das、S.M. Cioaba和W.H. Haemers等教授的关注和解决； 研究了完全k部图的D-谱特征问题，提出关于此图的猜想得到了国内图论专家张晓东教授等的证实；研究了T形树线图的Q-谱特征问题、3-玫瑰图的Q和L-谱特征问题、具有小谱半径图的Q和L-谱特征问题以及∞-图的A-谱特征。(2) 关于同谱图的研究，在研究特殊图的谱特征时，若此图不由其谱所确定，我们确定了其所有的同谱图；完全确定了两类图幷图的同谱类。(3)在相关专题的研究上，刻画了恰有三个Q-特征值至少2的连通图、最小D-特征值等于-2的连通图、直径为2时恰有三个不同D-特征值的图以及L-谱半径不超过4.5的连通图；研究了图的Q-特征值和汉密尔顿性之间的关系；给出了两类典型图的Hosoya指标和Merrifield指标的精准表达式；研究了新的图矩阵Radic矩阵的若干谱理论和Radic能量；确定了两类图色唯一的充要条件；给出一类平面图色多项的计算公式并研究了其色根的分布。(4) 在混合谱特征问题和一般图的研究上，用矩阵的方法给出了判定具有全部不同特征值的图的充要条件。