图的Q-谱与结构参数以及Q-谱的Turán型极值问题

The theory of graph spectra is an important field in combinatorics and graph theory. It investigates graphs and the relationship between graph spectra and graph invariants based on algebra theory and matrix theory. The signless Laplacian spectra, or Q-spectra for short, is an active branch in graph theory. D.Cvetkovic, S.K.Simic, et al play more attention on the Q-specra and intend to build a theory of graph spectra with respect to the Q-matrix. V.Nikiforov, F.Chung, et al aim to build extremal graph theory on a spectral basis, and they study the spectral Turán-type extremal problems. This project includes as follows.(1) Study the effect on the Q-spectra under some graph operations. Attempt to give the relations between the new Q-spectra and the original one after those operations. (2) Study the relationship between the Q-spectra and graph invariants. Attempt to give the bounds of some invariants in terms of the Q-eigenvalues. And for a given graph set with some invariant fixed, attempt to give an upper or lower bound for some Q-eigenvalue and characterize the structure of the graph which attain the bound. (3) Study the Q-spectral Turán-type extremal problems. Given a forbidden graph H, determine the largest or smallest eigenvalue of a graph with n vertices not containing the subgraph H. Consider some Turán-type theorems from extremal graph theory, attempt to give the Q-spectral conditions for the similar results.

图谱理论是组合数学与图论中一个非常重要的研究领域，它以代数理论、矩阵理论等为基础研究图的结构、以及图谱与图的其他参数之间的关系。无符号拉普拉斯谱，简称Q-谱，是图谱理论中一个非常活跃的研究分支。D.Cvetkovic和S.K.Simic等人对Q-谱进行了重点关注，欲将Q-谱理论形成一个体系，V.Nikiforov和F.Chung等人结合图谱理论和极值图论，研究了图谱的Turán型极值问题。本项目将做以下工作：(1) 研究若干图的运算对图的Q-谱的影响，给出运算后Q-谱的变化规律。(2) 研究Q-谱与图的结构参数之间的关系，用图的Q-特征值来界定某些结构参数，给出特殊图类中关于某个Q-特征值的界，并刻画达到该界的极图。(3) 研究Q-谱的Turán型极值问题，考虑给定的禁图H，求不含H作为子图的n阶图的最大(或最小)特征值的极值，考虑极值图论中的一些Turán型结果，将条件用Q-谱的形式给出。

本项目主要研究图的无符号拉普拉斯谱，即Q-谱。取得如下成果：.1、关于H-join 运算与图的Q-谱. (1) 给出了正则图的H-联图的Q-谱和H-联图的其他谱，并讨论了同谱以及整图的条件。. (2) 给出了基于一类图的H-联图的距离谱、距离拉普拉斯谱和距离Q-谱的特征多项式，并构造了这三种谱的许多同谱对，否定回答了“是不是每一个图由它的距离拉普拉斯谱或距离Q-谱决定(Aouchiche和Hansen，2013)”。.2、关于图的Q-谱确定性. (1) 研究了锥图G∨Ks 的Q-谱确定性，这里G是n阶r-正则图，Ks为s 阶完全图。证明了，对于任意正整数s，当r=n-2(n≥4) 时，G∨Ks 由其Q-谱确定；当r=n-3(n≥6) 时，G∨Ks 由其Q-谱确定当且仅当G的补图不含三角形。. (2) 研究了基于圈和三个孤立点的冠图的Q-谱确定性，证明了当n≠32,64,128时，该冠图由其Q-谱确定。.3、关于图的Q-特征值. (1) 基于n阶二部图和s 阶完全图，对于任意给定的正整数s 和正偶数n, 构造了最小Q-特征值为s 的一类 n+s 阶图。 对于任意给定的最小度δ和阶数n, 构造了最小Q-特征值为δ-1 的一类n 阶图。. (2) 利用图的结构参数——星匹配数，给出了第k大特征值的一个界，并给出了判断图的哈密顿性的一个谱条件。.4、关于连通奇二部k-一致超图的谱. 奇二部超图是普通超图的推广，我们证明了连通k-一致超图G的拉普拉斯H-谱和无符号拉普拉斯H-谱相同的充要条件是k为偶数且G为奇二部的；同时刻画了连通k-一致超图，使得其拉普拉斯谱半径和Q-谱半径相同，这样也就对问题“刻画拉普拉斯谱半径和Q-谱半径相同的条件(L. Qi，2014)”提供了一个解决方案。.5、 关于子图嫁接运算对二部图能量的影响. 得到了子图嫁接运算作用在二部图上其能量的变化规律，刻画了阶数和控制数固定的树集中，能量第三小和第四小的树的结构。