超欧拉图相关问题及方法研究

The supereulerian graph problem was proposed by Boesch, Suffey and Tindel in 1977. This problem and its related research field have lots of research findings and applications. However, the research in the fields of the supereulerianity of graphs with a restriction on small bonds, the k-supereulerian graph problems and the supereulerian problems in digraphs is very limited. Therefore, the research of these problems is significant in both theory and practice.. In this item, we will study the following four problems related to the supereulerian graph problem. Firstly, we will study the supereulerianity of graphs with a restriction on small bonds. A series of results have been obtained in this field, most of which are applied in the Hamilton-connectedness of line graphs. We will attempt to solve the conjecture of C(17,0) proposed by Lai et. al. Secondly, we will study the number of components of spanning even subgraph. This problem is closely related to the number of components of even factor and 2-factor of line graphs, and the Traveling Salesman Problem (TSP). Thirdly, we will give a characteristic of a graph while its iterated line graph has a Hamilton path, and give some bounds on Hamilton path index. Finally, we will study the supereulerian problem in digraphs, and discuss the relationship between supereuleian graphs and digraphs.. Our work will extend some prior results in the related research field. We will attempt to give some new methods and solve some open problems.

超欧拉图问题由Boesch、Suffey和Tindel在1977年提出。该问题以及与此相关的哈密尔顿问题等因子的存在性问题，研究成果众多，应用背景十分广泛。但是，在具有小键约束的超欧拉图问题、k-超欧拉图问题及有向超欧拉图问题上，研究成果还十分有限。因此，这些问题的研究具有重要的理论意义和实际意义。. 本项目拟从四个方面进行研究。首先，研究具有小键约束条件的超欧拉图问题，该问题已有一些已知结果，我们将尝试解决赖虹建等人关于C(17,0)的猜想；其次，研究生成偶子图的分支数界定问题，该问题与偶因子和线图2-因子的分支数、旅行售货员问题（TSP）等密切相关；第三，研究迭代线图中哈密尔顿路的存在性问题；最后，研究有向超欧拉图问题，讨论该问题与无向超欧拉图研究之间的联系。. 本项目计划对以上四个问题进行深入研究，在研究方法上有所突破，并尝试解决一些公开问题。

超欧拉图问题在图论的研究中有着广泛的应用，一直是图论研究的一个热点问题。在具有小键约束条件的超欧拉图问题、k-超欧拉图问题及有向超欧拉图问题上，研究成果还十分有限。本项目在以上这些领域，以及与此问题密切相关的哈密尔顿问题等因子的存在性等问题的已有结果的基础上，着重做了以下几个方面的研究。. 第一，在熊黎明等人研究迭代线图的哈密尔顿性的特征刻画及哈密尔顿指数等成果的基础上，给出了迭代线图中哈密尔顿路的存在性的特征刻画，提出了哈密尔顿路指数的概念，并且给出了若干哈密尔顿路指数的最好可能的上界。. 其次，研究了两个有向图的l-路和中的超欧拉图，给出了一些充分条件，这是对之前Alsatami等人研究两个有向图的2-和的推广，同时我们也给出了两个无向图的2-路和是超欧拉图的一个充分条件。. 第三，在李霄民等人研究广义棱柱的哈密尔顿性和超欧拉性的基础上，给出了几类常见的无向图的广义棱柱和补棱柱是超欧拉图的特征刻画，并且将广义棱柱的概念推广到有向图上，给出了两个有向图的广义棱柱是超欧拉图的若干充分条件。. 以上研究成果对于超欧拉图及有向超欧拉图的研究具有一定的理论价值。