有向超欧拉图及相关问题研究

Euler problem is a very old problem of graph theory.A (directed) graph is called supereulerian if there is a (directed) closed trace through all the vertices. The supereulerian problem on undirected graph became very popular since Catlin's reduction method was proposed. In this project, we study on supereulerian problem on digraphs. We start from the minimum degree condition and the connectivity condition for a digraph to be supereulerian. Then depicte the supereulerianness of a digraph gradually, including local structural characterization for a digraph to be supereulerian and forbidden subgraph structure characterization for a digraph to be supereulerian, etc., and give the algorithms to find the spanning eulerian subgraph under these sufficient conditions. Also, we will try to give a reduction method for digraphs, which might be very defferent from Catlin's undirected version. Finally, we present spanning (edge/arc) connectivity concept by combining supereulerian problem and connectivity of (directed) graphs, which allow us to apply the method of studying (directed) graph connectivity to supereulerian problem of (directed) graphs. We will study the essencial connection of these two problems. The research has a very closed relation to directed Hamilton problem and undirected super eulerian problem.

欧拉问题是图论中非常古老的一个问题，一个(有向)图称为超欧拉图是指存在一个(有向)闭迹通过图中所有点.对无向图，自Catlin提出约化方法以后超欧拉问题变得非常热门. 本项目拟研究有向图上的超欧拉问题，从最小度和连通度充分条件入手，逐步刻画有向图的超欧拉性，包括局部结构性刻画与禁止子图结构刻画等, 并给出在这些条件下寻找支撑欧拉子图的算法. 同时，借鉴Catlin的思想提出适用于有向图的约化方案，建立有向图超欧拉问题的一个一般性方法；最后，拟把(有向)图的超欧拉问题与(有向)图连通度结合起来，提出支撑(边/弧)连通度的概念，拟把研究(有向)图连通度的方法应用到(有向)图的超欧拉性上面，并研究这两个问题之间的本质联系. 该问题的研究与有向哈密尔顿问题以及无向图上的超欧拉问题密切相关.

欧拉问题是图论中十分古老且经典的问题，一个图称为超欧拉的如果它包含一个支撑欧拉子图。由于超欧拉问题提供了Thomasson猜想的一种研究思路，因此倍受大家关注。但是有向超欧拉图方面的研究相对较少，本项目从最小度条件入手研究有向超欧拉图的相关问题，主要证明了如果有向图的最小出度与最小入度的和至少为点数减4，则要么是超欧拉有向图要么属于两类特定的图类，该结论为有向超欧拉图的第一个结果，围绕此条件，我们进一步展开研究，给出了最小度和条件，以及对定向图也相应给出了存在欧拉因子的充分必要条件，利用该条件可以构造出许多最小度很大但不是超欧拉图，并且利用正则引理进一步将欧拉因子转换为支撑欧拉子图。同时，对独立数较小的图也给出了连通度充分条件，该条件解决了Jackson猜想在独立数为2时的特殊情况。关于最长圈问题，给出了一个3连通3正则图的最长圈的一个下界。同时还研究了分数支撑树打包与覆盖问题与图谱之间的关系。