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

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

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.