图中最长圈及相关问题的研究

In this project, we focus on the following two problems: (1)Determine a lower bound of the length of longest cycles of cubic graphs, and try to consider the problem when G is planar or Petersen-minor free or cyclic 4-edge connected. This research is related to a conjecture of Bondy and Jackson that there exists a constant c>0 so that every cyclic 4-edge connected cubic graph on n vertices has a cycle of length at least cn.(2)The problem proposed by Bermond and Lovász that is there an integer k such that every strongly k-connected digraph D has a dicycle containing any two prescribed two vertices. For oriented digraph, Jeager conjectured k should be at most 3. In this project, we try to answer or partially answer the above two problems.

本项目主要研究以下两个问题：(1) 3连通3正则图G的最长圈的长度的下界，以及该问题在G是平面图或者不含Petersen-minor或圈4边连通等条件下的研究. 此研究与Bondy和Jackson猜想密切相关，即：存在一个常数c>0使得任意一个阶数为n的三正则圈4边连通图都存在一个圈长度至少为cn.(2) Bermond和Lovász 提出的问题：是否存在一个整数k使得任意k强连通有向图D以及任意两个点x,y,都存在一个有向圈包含x和y? Jeager猜想该问题对定向图在k≤3时成立. 本项目尝试解决或者部分解决上述问题.

最长圈问题一直以来都是图论中非常重要且十分困难的问题，项目主要围绕Thomasson猜想(任意4连通线图是Hamiltonian的)与Bondy-Jackson猜想(存在一个常数c使得任意圈4边连通3正则图存在一个长度至少为cn的圈)，研究线图的最长圈问题。主要证明了任意3连通3正则图G以及G的任意两条边e,f, 都存在一个包含边e,f且长度至少为n^0.8的圈。研究过程中，发现了一种研究Thomasson猜想的一种新方法，即只要在原图中能找到一颗支撑树与一颗与之边不相交的边控制树，则对应的线图一定是Hamiltonian的，该条件与之前已知的条件(存在两颗边不相交的支撑树)要弱很多，因此项目还研究了边控制树的存在性的问题。我们给出了一些存在两颗边不相交的边控制树的必要条件和充分条件。.同时还从不同的角度给出了边不相交支撑树的存在性的一些充分条件，比如用图的特征值来刻画边不相交支撑树的存在性等，该结论解决了Ciaba和Wong的一个相关猜想；还给出了存在k个完全独立支撑树的充分条件等。此外, 对有向图，给出了强连通有向图的度序列的一个刻画，并且给出一个例子来说明2强连通要比强连通难得多。