基于图的不变量与子图结构的谱极值问题研究

Spectral graph theory mainly studies structure properties of graphs using the spectrum of related matrices, and now it is an important subject concerned commonly by algebraic graph theory and combinatorial matrix theory. The program will develop two field of intensive study on spectral extremal value problem. One is spectral extremal value problem based on the invariants of graphs, i.e., characterizing extremal value or extremal graph of spectral parameter in a given set of graphs with some fixed invariant of graph, and investigating the connection between eigenvalues of graphs and all kinds of invariants of graphs (e.g. clique number, chromatic number, independence number and diameter). The eigenvalues of graphs have good algorithm, however the computation complexity of some invariants of graphs (e.g. independence number and clique number) is NP-hard, and hence it is very necessary to develop the research.The other is spectral extremal value problem based on subgraph structure, that is to say, determining extremal value of spectral parameter in a given set of graphs including or forbidding some subgraph (e.g. complete subgraph, complete bipartite subgraph, path and cycle with given length, Hamilton cycle and path, and so on), for example, spectral forms of Turán and Zarankiewicz type problems, and studying the relation between eigenvalues of graphs and the existence of some subgraph. This project will use synthetically the methods of graph theory and matrix theory, adopt the research scheme combining theory derivation with computer verification, and exploit and enrich the research tools of spectral graph theory in order to promote the above problems solved successfully.

图谱理论主要通过研究图的相关矩阵的谱性质来反映图的结构性质，是当前代数图论和组合矩阵论共同关注的一个重要课题。本项目拟对图的谱极值问题开展两方面的深入研究。第一，基于图的不变量的谱极值问题：即刻画图的不变量固定的图类中谱参数的极值或极图，研究图的特征值与各种不变量(如团数、色数、独立数、直径等)之间的联系。图的特征值具有好算法，而图的某些不变量如独立数及团数的计算是NP-困难的，因此这方面的研究是很有必要的。第二，基于子图结构的谱极值问题：即确定包含或者禁用某种子图(如完全子图、完全二部子图、给定长的路和圈、Hamilton圈和路等)的图类中谱参数的极值，如谱形式的Turán型和Zarankiewicz型问题，研究图的特征值与某种子图存在性之间的关系。本项目将综合运用图论和矩阵论方法，采用理论推导和计算机验证相结合的研究方案，挖掘和丰富谱图论研究的工具，以期推动上述问题的顺利解决。

图谱理论是图论研究中一个非常活跃而又重要的研究领域，它在量子化学、统计力学、通信网络、计算机科学、图像处理和模式识别中均有着广泛的应用。图谱理论主要通过研究图的相关矩阵的谱性质来反映图的结构性质，是当前代数图论和组合矩阵论共同关注的一个重要课题。谱极值问题是近年来图谱理论的研究热点。作为极值图论的谱拓展，它主要研究图的各种矩阵表示的极端谱参数。本项目对图的谱极值问题开展了两方面的深入研究。第一，基于图的结构参数的谱极值问题：即刻画图的结构参数固定的图类中谱参数的极值或极图，研究了图的特征值与图的各种结构参数之间的关系。第二，基于子图存在性的谱极值问题：即确定包含或者禁用某种子图的图类中谱参数的极值。受本项目资助，共发表SCI论文14篇。本项目的代表性成果如下：(1) 刻画了悬挂点数固定的非二部单圈图中无符号拉普拉斯最小根达到最小的唯一极图；(2) 在符号矩阵的意义下，刻画了悬挂点数固定的非奇异混合图中第一特征根达到最小的唯一极图；(3) 分别提供了二部图和一般图含有Hamilton圈和Hamilton路的邻接谱半径和无符号拉普拉斯谱半径条件。总之，本项目的两方面研究任务与国内外谱极值理论的前沿领域有着密切的联系，具有重要的理论研究意义和广泛的应用价值。