图的距离矩阵的惯性及极端负特征值的研究

The distance matrix of a graph is a real symmetric square matrix containing the distances, taken pairwise, of the set of vertices. The matrix has come up in several different areas, including communication network design, graph embedding theory, molecular stability and network flow algorithms. This subject will use the algebraic theory, combining the structural properties of graphs with matrix theory (especially the non-negative matrix theory and combinatorial matrix theory) to study the inertia (the inertia is defined as the ordered triple whose components are respectively the numbers of positive, zero, and negative eigenvalues of a matrix) and extreme negative eigenvalues(minimum negative eigenvalue、maximum negative eigenvalue ) of the distance matrices of some regular graphs、k-cyclic graphs and their line graphs、some plane graphs and their inner dual graphs (ignore multi-edges). By developing new methods and techniques, we will get the inertia of the distance matrices and the inequality relationship betwwen the extreme negative distance eigenvalues and other parameters of these regular graphs, respectively; Determine if the distance matrices of k-cyclic graphs and their line graphs have the same positive inertia index and nullity; Determine the relationship betwwen the nullity of the distance matrices of these plane graphs and their minimum odd cycles. Our new results will enrich the distance spectral theory of graphs.

图的距离矩阵是由顶点对之间的距离构成的实对称方阵。这个矩阵出现在包括通信网络设计、图形嵌入理论、分子稳定性、网络流算法等在内的几个不同的领域中。本课题将利用代数理论，结合图的结构性质以及矩阵论（尤其是非负矩阵论和组合矩阵论）来研究若干正则图、k-圈图及其线图、若干平面图及其内对偶图（忽略重边）的距离矩阵的惯性（这里，惯性是指由矩阵的正特征值的个数、零特征值的个数及负特征值的个数构成的三元有序数组）及极端负特征值（最小负特征值、最大负特征值）。通过发展新的方法和技巧，我们将分别得到一些正则图的距离矩阵的惯性及极端负特征值与其它参数的不等式关系；确定各种k-圈图与其线图的距离矩阵是否具有相同的正惯性指数及零度；确定各种平面图的距离矩阵的零度与其极小奇圈的关系。我们的新结果将进一步丰富图的距离谱方面的理论。

本课题利用代数理论，结合图的结构性质、矩阵论、组合矩阵论研究了一些图的线图的距离矩阵的惯性、距离能量、同谱图、邻域冠图的谱不变量等问题。在基金委的资助下，目前已完成主要内容，取得了一些研究成果，达到了预期目标。主要内容和成果包括：（1）研究了单圈图的线图的距离矩阵的惯性、行列式的公式及能量，得到了单圈图及其线图具有相同的正惯性指数及0特征值重数，并且分别还确定了在所有单圈图的线图中取得极大、极小距离能量的图；（2）构造了一类同谱图，其补图、线图也是同谱图，而且它们的距离矩阵也有相同的谱，这是McKay的一个结论的推广。 除此之外, 我们还可以要求这些图有相同的拉普拉斯谱；（3）得到了邻域冠图的惯性、电阻距离等谱不变量。