图的谱刻画与极端图谱研究

The graph spectum mainly studies other combinatorial property of a graph through spectral characterization (the multiset of eigenvalues) of some matrices associated with the graph such as adjacency matrix, Laplacian matrix, signless Laplacian matrix etc. It is not only a cross field of graph theory, combinatorics, matrix theory and algebra theory, but also a branch of algebraic graph theory. It also has a wide range of applications in graph theory, physics, quantum chemistry, computer science, internet technology etc. This project is focus on the problem of spectral characterization of graphs and the property of structure and spectrum of graphs whose number of distinct eigenvalues are maximum (all are distinct) or minimum (the number of distinct eigenvalues is between 3 and 5). It involves the following four research areas:.1.Study the graph structure and spectrum with some given eigenvalues or eigenvectors..2.Research the graphs determined by their adjacency spectrum, or Laplacian spectrum, or signless Laplacian spectrum by some algebraic method and technique; for the non-determined by the spectrum graphs, complete their spectral characterization; discover new method for costructing cospectral graphs..3.Find the new graphs with distinct eigenvalues or the grahps with the number of distinct eigenvalues minimum..4.Study the structure, spectrum of graphs whose number of distinct eigenvalues are maximum or minimum, link their spectrum and other graph parameters.

图谱主要通过研究与图相关的矩阵(邻接矩阵, 拉普拉斯矩阵, 无符号拉普拉斯矩阵等)的谱(特征值的多重集)的性质来研究图的其它组合性质. 图谱是图论, 组合论, 矩阵论的一个交叉领域, 在图论自身, 物理, 量子化学, 计算机科学, 互联网技术等方面有着广泛的应用. 本项目着重研究图的谱刻画问题及不同特征值数达到最大(特征值全部互异)和最小(不同特征值数介于三到五之间)的图的结构性质及谱性质, 主要涉及以下四方面研究内容:.1.研究满足某些特征值或特征向量条件的图的结构性质与组合性质..2.利用代数方法与技巧研究由图的邻接谱, 拉普拉斯谱, 无符号拉普拉斯谱确定的图; 对于非由谱确定的图完成其谱刻画; 探索新的构造同谱图的方法..3.寻找特征值全部互异及不同特征值数达到最小的新图类..4.研究特征值全部互异与不同特征值数达到最小的两类极图的结构, 谱性质及图谱与图的其它参数间的关系.

通过将代数图论方法与图的计数理论方法相结合, 并引入两个计算图的Q-特征多项式的新公式, 我们对图的谱刻画问题及具有极端不同特征值数目图的问题进行了研究, 取得的成果主要包括(1)证明了所有的θ-图和哑铃图都是由它们的拉普拉斯谱所确定的, 并且通过例子说明不是所有的含唯一四圈的θ-图由它的邻接谱所确定. (2) 给出了计算图的Q-特征多项式的两个似Schwenk-公式, 利用此公式得到了没有两个不同构的棒棒糖图是Q-同谱的一种简单证法. (3) 给出了任意图中长度不超过6的道(walk)数目的计数公式, 并且由此得到了图广义同谱的新的不变量. (4)证明了长度为3或4的扩展路是由它们的广义谱所确定. (5) 完成了对第二大特征值不超过1的单圈图的谱刻画.