非二部图的最小无符号拉普拉斯特征值的研究

The signless Laplacian spectrum of a graph is a common research topic of algebraic graph theory and combinatoric matrix theory, and has important theoretical significance and broad applications. Desai and Rao proved that the least eigenvalue of the signless Laplacian of a graph can measure the non-bipartiteness of the graph. So it is a very important eigenvalue of a graph. However, less research results can be found on this eigenvalue till now. In this project, we are concerned with the least eigenvalues of the signless Laplacian of non-bipartite graphs, and wil deeply study the corresponding eigenvector and characteristic polynomial of the signless Laplacian matrix. We attempt to find out some new methods to study the eigenvalue better. Based on this, we will investigate how the least eigenvalue changes by graph operations, and focus on the relations between the least eigenvalue and some invariants which reflect the structure of the graph.

图的无符号拉普拉斯谱是代数图论和组合矩阵论共同关注的一个研究课题，具有重要的理论意义和广泛的应用价值。Desai，Rao等人证明了最小无符号拉普拉斯特征值可以非常有效的衡量图的非二部性, 因此最小无符号拉普拉斯特征值是图的一个非常重要的特征值，但是目前关于它的研究成果却非常少。本课题主要研究非二部图的最小无符号拉普拉斯特征值问题。项目拟对图的无符号拉普拉斯矩阵所对应的特征向量及特征多项式进行系统的研究,找到一些研究最小无符号拉普拉斯特征值的新方法，并以此为基础来研究图的变形对最小无符号拉普拉斯特征值的影响，以及最小无符号拉普拉斯特征值与图的结构参数之间的关系。

本课题研究了图的无符号拉普拉斯（Ｑ-）特征值，并取得了一系列的研究成果。. 首先，是关于最小Ｑ-特征值的上界的研究。（1）给出了最小Ｑ特征值的一个与控制数有关的可达的上界，并刻画了达到上界的充要条件。（2）研究了基于n阶二部图和s阶完全图构造的一个图类，得到了该图类的最小Ｑ-特征值的一个可达上界为s。 基于此, 对于任意给定的正整数s和正偶数n， 构造了最小Ｑ-特征值为s的一类n +s阶图。. 其次，是关于第k大Ｑ-特征值的研究。（1）利用图的星匹配数给出了第k大Ｑ-特征值的一些界，从而给出了判断一个图是哈密尔顿图的Ｑ-特征值条件。（2）研究了删点集对图的Ｑ-谱的影响，给出了删点集插值定理。进一步，得到了第k大Ｑ-特征值与第k大度相关的一个下界，以及等号成立的必要条件。 . 再次，是关于Ｑ-谱确定性的研究。（1）利用图的操作构造了一些Ｑ-谱确定的图，证明了１-正则、（ｎ-２）-正则图与K2并接后所得图是Ｑ-谱确定的，（ｎ-3）-正则图与K2并接后所得的图是Ｑ-谱确定的当且仅当（ｎ-3）-正则图中不含三角形。（2）确定了图经广义并接后的Ｑ-特征多项式和Ａ-特征多项式，构造了很多对Ｑ-同谱图，并给出了一些关于特殊图类的Ｑ-特征值和Ａ-特征值的不等式序列。. 然后，是关于距离谱的研究。给出了图经广义并接运算后所得图的距离特征多项式、距离Ｌ-特征多项式、距离Ｑ-特征多项式，并构造了无穷多对距离谱同谱对，距离Ｌ-谱同谱对和距离Ｑ-谱同谱对。. 另外，我们还研究了图的Ｌ-特征多项式系数，确定了二部双圈图中Ｌ-特征多项式系数最小的图。