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

项目名称： 图的距离矩阵的惯性及极端负特征值的研究

项目编号： No.11501491

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 张小玲

作者单位： 烟台大学

项目金额： 18万元

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

中文关键词： 距离矩阵；惯性；正则图；k-圈图；平面图

英文摘要： 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.

英文关键词： Distance matrix;Inertia;Regular graph;k-cyclic graph;Plane graph