有向超欧拉图的度条件及相关问题研究

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 for a digraph to be supereulerian. Then depicted the supereulerianness of a digraph gradually, including minimum degree condition, degree sum condition, degree sequence condition arc-condition and Ore-type condition ect.. Also, we will try to improve the lower bound of these conditions under the case that D is under some connectivity-condition. The research has a very closed relation to directed Hamilton problem and undirected super eulerian problem.

欧拉问题是图论中非常古老的一个问题，一个(有向)图称为超欧拉图是指存在一个(有向)闭迹通过图中所有点. 对无向图，自Catlin提出约化方法以后超欧拉问题变得非常热门. 本项目拟研究有向图上的超欧拉问题，从最小度充分条件入手，逐步研究有向图或定向图是超欧拉图的充分条件, 包括最小度条件, 度和条件, 度序列条件, 弧数条件, Ore-型条件等. 同时, 在某些连通性的条件下来优化这些条件, 该问题的研究与有向Hamilton问题以及无向图上的超欧拉问题密切相关.

设D为有向图, 如果D存在一个有向闭迹通过D的所有点, 则称D为超欧拉的. 我们证明了对任意有向图D, 如果最小度至少为4, 且最小出度到最小入度的和至少为图D的点数减4, 则D要么是超欧拉要么属于特定的一类图. 而且对Ore型度和条件也给出了类似的结论, 证明了对任意两个点u,v, 如果uv没有弧, 且u的出度与v的入度的和至少为D的点数减4, 则D要么是超欧拉要么属于特定的两类图. 项目所计划的任务基本完成.