图的零强迫数、最小秩、最大零度及其相关问题研究

The minimum rank problem for a graph is to determine the minimum rank and the maximum nullity among all matrices governed by the graph over a given field. To better study this problem, AIM Minimum Rank-Special Graphs Work Group introduces a structure parameter of a graph, which is called the zero forcing number of a graph. In this proposal, we focus on the properties of the zero forcing number, the minimum rank, the maximum nullity of a graph and their relationship with the structure of the graph. Based on this theory, we calculate the zero forcing number, the minimum rank and the maximum nullity of some important and meaningful graphs, or determine their extremal values and characterize the extremal graphs. The main content of this proposal contains the following: Firstly, we show the zero forcing number is equal to the maximum nullity for threshold graphs (resp. subdivided graphs); and characterize the graphs whose zero forcing number is equal to the maximum nullity in the set of all generalized cycle star graphs, double generalized cycle star graphs and cacti, respectively; Secondly, graphs are characterized when the zero forcing number is a given important value; the minimum and maximum zero forcing number among 2-connected garphs (resp. cacti) are determined and the exremal graphs are characterized, respectively; Finally, the zero forcing number, the minimum rank and the maximum nullity of directed graphs whose underlying graphs are butterfly network (resp. subdivided graphs) and their related problems are studied. The research of this proposal will further promote the study of the minimum rank problem for a graph and improve the research level of algebraic graph theory in China.

图的最小秩问题是在给定的数域上，确定图的最小秩和最大零度。为了更好地研究这一问题，AIM Minimum Rank-Special Graphs Work Group 引入了图的结构参数——图的零强迫数。本项目集中研究图的零强迫数、最小秩、最大零度的性质以及它们与图结构之间的关系。以此作为理论依据计算一些重要而有意义的图的零强迫数、最小秩和最大零度或研究它们的极值问题并刻画极图的结构。研究内容主要包括：（1）分别证明门槛图和细分图的零强迫数与最大零度相等；分别刻画广义圈星图、双广义圈星图和仙人掌图中零强迫数与最大零度相等时图的结构；（2）刻画零强迫数为一些重要值时图的结构；分别确定2-连通图和仙人掌图的零强迫数的极值并刻画极图的结构；（3）研究底图是蝶形网络、细分图的有向图的零强迫数、最小秩、最大零度及其相关问题。本项目的研究将进一步推进图的最小秩问题的研究，推动我国代数图论的研究水平。

图的最小秩问题是在给定的数域上，确定图的最小秩和最大零度。为了更好地研究这一问题，AIM Minimum Rank-Special Graphs Work Group引入了图的结构参数——图的零强迫数。本项目集中研究图的零强迫数、最小秩、最大零度的性质以及它们与图结构之间的关系。以此作为理论依据计算一些重要而有意义的图的零强迫数、最小秩和最大零度或研究它们的极值问题并刻画极图的结构。首先，我们研究了有向图的零强迫数。刻画了零强迫数为一些重要的特殊值时图的结构特征，解决了Caro, Davila 和Pepper于2019年在论文Extremal forcing sets in oriented graphs中提出的一个开放问题。更一般地，确定了有向图中四类零强迫数和四类Grundy 控制数之间的关系；给出了在有向图中分析k-power 控制过程和k-强迫过程的一种新方法。在此基础上，我们还研究了有向图的子图收缩对其k-power 控制数和k-强迫数的影响。基于对图的k-强迫过程的探讨，我们进一步研究了图的全k-强迫数。首先研究了图的全k-强迫数的一些基本性质，在此基础上，刻画了具有较大的全k-强迫数的图的结构特征，还确定了给定最大度的图中全k-强迫数的上界。与此同时，我们研究了图的全k-强迫数与图的各种控制数之间的关系。此外，考虑到图谱问题和最小秩问题作为代数图论中非常重要的两个研究内容，均着眼于图的特征值、特征向量等代数特征的研究，而图参数的极值问题研究的相关结论，通常对图的谱参数的研究具有引导性，我们也研究了树、仙人掌图、连通图和连通二部图的图参数以及Cayley图的谱参数。相关研究成果将更好地推进图的零强迫数、最小秩、最大零度的问题的研究，也进而对我国代数图论的发展产生积极的影响。