关于有向图的谱半径和子图存在性的研究

Caccetta and Haggkvist in 1978 conjectured that every digraph on n vertives with minimum outdegree at least n/r has a directed cycle of length at most r. Later, in 2005, Charbit posed a stronger conjecture, that is, every digraph on n vertives with spcetral radius at least n/r has a directed cycle of length at most r. These two conjectures are still open and many related problems were posed by many reseachers. In this project, we consider three of them: Firstly, does a digraph on n vertives with minimum outdegree and indegree at least n/r has a directed triangle; Secondly, giving a spectral radius conditions, such that the digraph contains a (directed) cycle of length k or a (directed) path of length k? Thirdly, Finding an orientation, such that a simple connected graph under this orientation attains the maximum spectral radius? Moreover, we also consider several related problems of the three problems mentioned above, such as, the existence of the subgraph and the girth of digraphs and so on. This project will use synthetically the methods of graph theory, matrix theory and Regular Lemma, adopt the research scheme combining theory derivation and computer verification, and exploit and enrich the research tools of graph theory in order to promote the above problems solved sucessfully.

1978年，Caccetta 和 Haggkvist 猜想出度不小于n/r的有向图包含长度不超过 r 的有向圈，其中n为图的顶点数，r 为正整数。在2005年，Charbit 提出了比 C-H 猜想更强的一个猜想：谱半径不小于n/r的有向图含有圈长不超过r的有向圈。这两个猜想至今未被解决且引申出诸多研究课题，本项目关注如下三个问题，其一，出度和入度均不小于n/3的有向图是否包含有向三角形？其二，给出有向图含有k-长（有向）圈或k-长（有向）路的谱半径条件？其三，在什么样的定向方式下，使得一个简单连通图的谱半径达到最大？这三个问题均是可扩展的，对它们的深入研究将引申出诸多后继课题，比如子图存在性问题，有向图的围长等问题。本项目将综合运用图论、矩阵论以及 Regular Lemma 等研究方法，采用理论推导和计算机验证相结合的研究方案，挖掘和丰富图论问题的研究工具，以期推动上述问题的顺利解决。

图谱理论主要研究图的相关矩阵的特征值和特征向量，应用代数理论来研究图的拓扑性质，以及应用图的拓扑结构来研究图的谱性质。在本项目中，我们将对以下两方面内容展开研究。第一，有向图的谱半径与结构参数之间的关系；第二，关于图的距离特征值、子图存在和结构参数。特别地，我们深入研究了距离谱和图的结构参数相关问题，解决了本领域的一些猜想和公开问题，包括：1. 解决了Aouchiche和Hansen[Distance spectra of graphs: A survey, Linear Algebra Appl.]提出的关于距离最小根和直径的猜想。2. 解决了Aouchiche和Hansen[Proximity, remoteness and distance eigenvalues of a graph, Discrete Appl. Math.]提出的关于图的remoteness和图的距离特征值的猜想。3. 解决了Fajtlowicz[Written on the wall: conjectures derived on the basis of the program Galatea Gabriella Graffiti]提出的关于图的距离特征值与图中三角形个数的猜想。