图的惯性指数与结构参数关系的研究

The basic task of spectral graph theory is to study the structural properties of a graph via its spectral properties, thus realize the classic thought: using algebraic tools to study geometric objects. The algebraic tool used in this project is the inertia index of graphs (including rank of graphs, signature of graphs). Because of its attraction on algebraic experts and applications in quantum chemistry, it has become a hot topic in graph theory in recent years. The structural parameters considered in this project, such as the diameter, independence number, vertex cover number, domination number, matching number, and the number of odd cycles, are basic and important parameters in classic graph theory for their direct reflecting on structural properties.. In this project, we aim to study the relation between the inertia indices and the structural parameters of graphs. We try to solve some conjectures and open problems in this field. More explicitly, we will respectively study the relation between the rank and the order, the vertex cover number and the vertex domination number of graphs. We will also study the relation between the signature and the number of odd cycles of graphs, and the relation between the inertia indices and the diameter of graphs. Our work in this project will help enrich and develop the theoretical system of this field.

图谱理论的基本任务是通过对图的谱的代数分析，借以描述、刻画图的结构性质，是经典思想‘借助代数工具研究几何对象’在图论学科的具体体现。本项目所用的代数工具是图的惯性指数（包括图的秩、图的符号差），因其为代数专家所重视, 且在量子化学领域有应用背景，近年来成为图谱理论的研究热点之一。本项目的研究对象，包括图的直径、独立数、点覆盖数、点控制数、匹配数及奇圈个数，因为能直接反映图的结构性质，均是经典图论中常见的基本参数。. 本项目拟研究图的惯性指数与结构参数间的本质联系，力求解决该领域若干遗留问题和猜想。具体来说，我们将研究图的秩分别与阶数、点覆盖数及点控制数之间的关系；研究图的符号差与奇圈个数的关系；探寻图的正、负惯性指数与直径的关系，从而丰富和发展‘基于图的谱参数刻画图的结构性质’的理论体系。

图谱理论的基本任务是通过对图的谱的代数分析，借以描述、刻画图的结构性质，是经典思想‘借助代数工具研究几何对象’在图论学科的具体体现。其中对图的惯性指数的研究，因为与量子化学理论与密切关系，能体现图的结构性质，并且主要使用代数方法和技巧，因而是量子化学、组合学以及代数学共同关注的热点之一。. 本项目研究成果主要分为三类。一是刻画了一些图类的代数结构，这是我们在掌握传统方法的基础上，为解决图谱理论的相关问题提供了新方法、拓展了新视野。尤其是我们提出的Annihilator的概念，其实就是基于特征子空间维数提出的，我们发现这一工具与图结构以及特征值重数的密切联系，不仅帮助我们证明了零维数与阶数的一个重要猜想，还进一步被广泛应用到解决图在一般矩阵下的任意特征值重数的研究过程中。二是刻画了图的惯性指数与直径、点覆盖数、阶数、色数、最大度等多个结构参数的联系，极大丰富了‘图的秩与零维数’这一经典理论。三是借助Annihilator这一有力工具，推广经典‘图的秩与零维数理论’到有向图、一般矩阵、任意特征值的重数上，从而实现了已有经典理论在三个不同维度上的一般性推广，我们的工作引起了国内外学者的广泛关注，对简单图在A-Alpha矩阵下任意特征值重数的研究是当下图谱理论的热潮之一。