基于图的谱参数与结构参数的几类极值图论问题研究

The spectral graph theory is an important research field in graph theory. Studying the extremal problems based on spectral and structure parameters of graphs not only promotes the development for spectra theory, but also affords a strong tool for applying this theory to many other research fields. In recent years, it plays a key role in the research of statistical physics and quantum chemistry. In this proposal we mainly study the extremal problems which are closely related to spectral and structure parameters, and we hope to solve some challenging problems in algebraic graph theory. The main content of this proposal contains the following： Firstly, we mainly study the signed graph both for the extremal problems on the Colin de Verdière parameter and for the bounds of its Laplacian permanent. Secondly, we investigate the relation between the normalized Laplacian spectrum of non-regular lattice on the torus and the enumeration of spanning trees (resp. degree-Kirchhoff index et al) in the context of statistical physics. Thirdly, we study the spectral properties of Szeged adjacency matrix and Laplace Szeged matrix; as well some extremal problems based on the Szeged parameter are considered. Finally, we study the relation between the rank of a graph and its structure parameters; as well the relation between skew-rank of directed graph and the rank of its underlying graph is also studied. The research of this proposal will extend the connotation of the study on spectral graph theory, which will improve the research level of algebraic graph theory and combinatorial matrix theory in China.

图谱理论是图论的一个重要研究方向，研究基于图的谱参数与结构参数的极值问题，不仅能大力促进图谱理论自身的发展，而且为许多其他领域的发展提供有力的工具。本项目将研究基于图的谱参数与结构参数的几类相关极值问题，解决一些富有挑战性的代数图论问题。研究内容主要包括：⑴ 研究符号图Colin de Verdière参数的极值问题和符号图Laplace积和式的界；⑵ 重点研究统计物理背景下嵌入到环面上非正则格子图的正规化Laplace谱与支撑树数目、度-基尔霍夫指数等参数之间的关系；研究正规化Laplace特征多项式根的分布问题；⑶ 研究Szeged邻接矩阵、拉普拉斯Szeged矩阵的谱性质以及基于Szeged参数的相关极值问题；⑷ 研究图的秩与其它图参数之间的关系，并刻画定向图的斜秩与底图的秩之间的关系。本项目的研究将拓展谱图理论研究的内涵，进一步推动我国代数图论与组合矩阵论的研究水平。

图谱理论是图论的一个重要研究方向，研究基于图的谱参数与结构参数的极值问题，不仅能大力促进图谱理论自身的发展，而且为许多其他领域的发展提供有力的工具。本项目研究内容主要包括：.(1)研究complex unit gain graph（包括符号图、混图）的特征多项式、特征根的特性以及Laplace积和式。具体研究了随机符号图的能量、确定了八边形链积和多项式系数和的极值并刻画了对应极图的结构; 进而研究了苯基链的积和多项式系数和、谱半径、H-不变量以及M-S不变量的一些极值图论问题;研究了混图与unit gain graph的特征根重数问题..(2)研究基于正规化Laplace谱的相关极值图论问题。首先，给定图G,经过变换得到图H。主要研究图H与图G的一些统计量之间的关系。其次，利用规范化拉普拉斯谱理论，对一些图类，比如五边形链、六角形链、苯基链及其衍生物等的基尔霍夫指数、度积基尔霍夫指数、Kemeny 常数、支撑树数目以及电阻距离等给出了显示表达式。最后，还初步探讨了基于图上随机游走的一些极值图论问题。.(3)研究基于距离条件下的某些结构参数和距离矩阵的谱参数的极值图论问题。首先系统研究了图的离心距离和. 在给定某些参数的树、二部图以及一般图，我们刻画了离心距离和的上、下确界. 其次，研究了(修正的)Szeged指数与Wiener指数之间的关系。一方面建立了(修正的)Szeged指数与Wiener指数之差的上、下确界，刻画了对应的极图，另一方面还解决了著名图论学者Hansen教授提出的三个猜想；第三，我们建立了距离谱半径和图的一些结构参数之间的联系，进而解决了有关离心率矩阵最大特征根和最小特征根的两个猜想。.(4)首先研究了定向图及混图的秩分别与底图的秩、底图的独立数、匹配数之间的关系。其次，研究了赋权图的正负惯性指数之间的关系、赋权混图的H-秩及其特征多项式等的秩与其它图参数之间的关系。.本项目的研究将拓展谱图理论研究的内涵，进一步推动我国代数图论与组合矩阵论的研究水平。上述成果均发表在本领域国际权威期刊上。详情请参见附录。