图的哈密尔顿性的谱刻画

It is an important NP-complete problem in structure graph theory to judge whether a graph is Hamiltonian. So far there is no perfect description to this problem. Therefore, it has always been concerned by the workers of graph theory and the mathematics, and explored the new method for characterization of Hamiltonicity of graphs. Recently, relying on the spectrum of matrix representation of graph, giving the spectral sufficient conditions of the Hamiltonian graph has been a new method to study the Hamilton problem, and it has produced many new results.. Combining the theories and methods of structure graph theory and algebraic graph theory, this project will give some sufficient or necessary conditions for a graph to be Hamiltonian. The research contents include combining the ideas from theorems of Ore and Fan to develop extremal spectral conditions for dense graphs with given connectivity, toughness, forbidden subgraphs to be Hamiltonian (and related structural properties ). Using the spectrum of the graph and corresponding eigenvector to explore some sufficient or necessary conditions for sparse graphs with some property to be Hamiltonian (and related structural properties). Studying extremal spectral conditions for oriented graphs to be Hamiltonian. The research of this project will build a bridge between structure graph theory and algebraic graph theory. Expected results not only enrich the study of Hamilton problem in structural graph theory, but also extend the spectral study of algebraic graph theory, thus promoting the research of algebraic method of Hamilton problem.

判断一个图是否为哈密尔顿图是结构图论中的一个重要的NP-complete问题，至今没有一个完美的刻画，因此一直受到图论及数学工作者的关注，并探索图的哈密尔顿刻画的新方法。近年来，借助于图的矩阵表示的谱，给出哈密尔顿图的谱充分条件，已成为研究哈密尔顿问题的新方法，并产生诸多新结果。. 本项目综合应用结构图论和代数图论的理论与方法，给出图具有哈密尔顿性的充分或必要条件，研究内容包括：结合Ore定理和范定理的思想，寻找给定连通度、韧度、禁止子图的稠密图为哈密尔顿图（及相关结构性质）的极值谱条件；利用图谱和特征向量，刻画具有某种性质的稀疏图是哈密尔顿图（及相关结构性质）的充分或必要条件；研究有向图为哈密尔顿图的极值谱条件。本项目的研究将在结构图论与代数图论建立一座桥梁，预期结果不仅丰富结构图论中哈密尔顿问题研究，而且将拓广代数图论的谱研究，从而推动哈密尔顿问题的代数方法研究。

应用图的相关矩阵的谱性质来刻画图的结构性质是当今国际代数图论与组合矩阵论研究的一个重要课题，而判定一个图是否具有哈密尔顿性是图论中困难问题之一，我们研究主要是利用图的谱性质来刻画图的哈密尔顿性，拓广了代数图论的谱研究，为解决哈密尔顿问题提供了一条新途径，具体研究成果体现在如下几个方面：. 1.哈密尔顿图的谱刻画. （1）我们研究了韧度为1，2或3的图的哈密尔顿性的谱刻画，给出了其是哈密尔顿图的谱半径和无符号拉普拉斯谱半径充分条件。. （2）我们研究了二部图的哈密尔顿性的谱刻画，给出了具有较大最小度的平衡二部图是可迹图或哈密尔顿图的谱半径充分条件，以及拟平衡二部图是可迹图的能量充分条件。. （3）我们通过优化哈密尔顿图的边界条件，进一步优化了利用图以及补图的谱半径和无符号拉普拉斯谱半径来刻画哈密尔顿图的充分条件。. 2.高哈密尔顿图的谱刻画. （1）我们研究了泛圈图的谱刻画，给出了最小度为2或3的图是泛圈图的谱半径和无符号拉普拉斯谱半径充分条件。. （2）我们研究了哈密尔顿连通图或从任一点出发都可迹图的谱刻画，给出了具有较大最小度的图是哈密尔顿连通图或从任一点出发都可迹图的谱半径和无符号拉普拉斯谱半径充分条件。. 3.哈密尔顿图相关结构性质的谱刻画. （1）我们研究了利用补图的谱半径给出具有较大最小度的图包含Cs ,Ps ,K2,sK2,或s-因子的充分条件。. （2）我们研究了单圈图具有最大和最小 Aα-谱半径的极值图，给出了单圈图具有最大 Aα-分离度的极值图。. （3）我们应用赋权关联矩阵和超边操作等方法，确定了具有第二或第三大谱半径的唯一线性单圈超图，. （4）我们研究了给定阶数的单圈图的最大拉普拉斯分离度，并刻画了相应的极图，其结果推广了当k=1,2,3的结论。. 总之，我们基本完成了本项目的研究内容，完成了目标任务，共计发表相关学术论文22篇，其中SCI收录12篇，EI收录2篇。