图的谱特征和色性问题及其关系研究

The Spectral Characterization Problem and Chromaticity Problem of graphs are the two of most difficult problems in the spectral graph theory and chromatic polynomial theory respectively. Schwank，van Dam，Haemers and Bollobás posed three famous conjectures about them, which haven't made much headway up to now. This funded project will focus on these two problems and three conjectures, and mainly investigate the special graphs, the generalized spectral characterization problem, the constructions of chromatically equivalent and unique graphs, general graphs and related topics. These two problems have important theoretical sense and applications, particllarly in the theory of algorithm complexity. There are two aspects of innovation: one is the novel research contents, including the new spectral graph theory, the generalizations of Schwank's result,the algebraic properties of adjoint polynomial, the characteristic polynomial on two variables, the Bartholdi-zeta-functions and their relations between these two problems. The other one is the novel research methods, containing the use of the Bartholdi-zeta-functions, eigenspace and eigenvector to study the Spectral Characterization Problem, and the new relations among the polynomials of graphs to study the Chromaticity Problem.

图的谱特征问题和图的色性问题分别是图谱理论和色多项式理论中的两个难题。Schwank、van Dam、Haemers和Bollobás等关于这两个问题提出了三个著名的猜想， 但至今仍无进展。本项目以这两个问题和三个猜想为核心展开研究，主要研究特殊图类、广义谱特征问题、色等价和色唯一图的构造、一般图和相关专题等五大方面。这两个难题的研究具有重要的理论意义和应用价值，尤其在算法复杂性理论方面。 项目有两方面的创新：一是新的研究内容：包括新的谱理论、推广Schwank的结论、伴随多项式的代数性质、双变量特征多项式和Bartholdi-zeta-函数以及二者之间的关系研究；二是新的研究方法：引入图的Bartholdi-zeta-函数、特征空间和特征向量研究图的谱特征问题；利用新发现的图多项式之间的关系研究图的色性问题。

主要研究图的谱特征问题、图的色性问题以及相关问题。得到的主要结果如下：(1)研究了图拉普拉斯特征多项式的系数与第一Zagreb指标的关系,给出了一般图第一Zagreb指标的下界并刻画了所有的极图,研究了具有较小第一Zagreb指标图的拉普拉斯谱特征。(2)关于图的特征值和图结构，刻画了第四大无符号特征值不超过1的连通图；刻画了第二大邻接特征值在区间的单圈图；刻画了第二大拉普拉斯特征值不超过3的符号图；证明了至多有两个（无符号）拉普拉斯特征值大于的图被其拉普拉斯谱所确定，除一个例外，这样图还被其无符号拉普拉斯谱所确定。(3)关于定向图的能量，刻画了具有前五大斜能量的定向双圈图；刻画了具有最大斜能量的定向三圈图。关于图的Randic能量，给出了图规范无符号拉普拉斯特征值和其剖分图Randic能量的关系，并得到星剖分图的Randic能量。关于拉普拉斯边界能量图，给出了一种新的构造方法，并确定了这样图阶数和边数的界，证明了大量的2连通图不是拉普拉斯边界能量图。(4) 研究了伴随多项式的次最小实根，找到了研究色唯一性的新方法；(5)提出并研究了一个新的图谱理论，即基于图离心率矩阵的谱理论，证明了树的离心率矩阵是不可约的。(6)在相关专题方面的研究，构造了字典积网络中边不交的Steiner路；给出了积网络线性k荫度的上下界；利用线图运算构造了一类小世界网络；刻画了具有较大广义（边）连通度的图。(7)在相关初步探索方面的研究，给出了自补图补图的彩虹点连通数；给出了图积彩虹连通指标的上下界；确定一类完全三部图的强公平点荫度等。