图的超欧拉性质和生成偶子图的分支数研究

The supereulerian graph problem: determine when a graph contains a spanning Eulerian subgraph, was proposed by Boesch, Suffey and Tindel in 1977. In 1988, Catlin presented the Reduction method and the Reduction theorem, which are effective tools in the research of supereulerian graphs. We extended the definition of supereulerian graph, proposed k-supereulerian graph, which contains a spanning even subgraph with at most k components, and proved the corresponding reduction theorem of k-supereulerian graphs. The main contents include the following. Firstly, we will study the extremal graph problems in k-supereulerians, and present some sufficient conditions for k-supereulerian graphs with constraint of degree condition, the order (the number of vertices) or the size (the number of edges). The k-supereulerian graph problem is closely related to the fields of the number of the components of even factor and 2-factor of line graphs, and the Traveling Salesman Problem(TSP). Secondly, according to a series of known results of the supereulerianity of graphs with a restriction on small bonds, most of which are applied in the Hamilton-connectedness of line graphs. We will discuss some larger graph families. It is hopeful to extend prior results.

图论中的超欧拉问题，即确定一个图是否包含生成欧拉子图，是由Boesch、Suffey和Tindel在1977年提出的。Catlin在1988年给出的约化定理是研究此类问题的一个重要工具。项目申请人提出了k-超欧拉图的概念，即包含至多k个分支的生成偶子图，并且已经推广了Catlin的约化定理。本项目拟从以下两个方面进行研究。首先，在已经得到的k-超欧拉图收缩方法的基础上，研究基于度条件、顶点数、边数等条件的生成偶子图分支数的界定问题。该问题与界定分支个数的偶因子、线图的2-因子、旅行售货员(TSP)等问题密切相关，可望推广一些已有结果，并在研究方法上有所突破；其次，研究具有小键约束条件的超欧拉图问题和k-超欧拉图问题，此类问题的已有结果已应用于线图的哈密尔顿连通性等领域，本项目拟在这些结果的基础上，适当放松约束条件，讨论更大范围图类上的超欧拉问题，可望推广已知结果。

本项目主要研究了以下图的超欧拉性质相关的两个问题。第一，生成偶子图分支数的界定问题。针对这个问题，我们完全解决了2-边-连通图的生成偶子图分支数界定问题，证明了如果一个2-边-连通图顶点数为n，且不含自环，那么这个图是⌈(n-2)/3⌉-超欧拉图，即包含一个分支数不超过⌈(n-2)/3⌉的生成偶子图，或者是一类反例图。这个界是最好可能的。应用这个结果，我们研究了边数条件下生成偶子图分支数的界定问题，最小度条件下偶因子、线图的2-因子分支数的界定问题，以及小键约束条件下的k-超欧拉图问题，给出了相应的结果。以上这些结果发表在2014年Discrete Mathematics上。第二，具有小键约束条件的超欧拉图问题。针对这个问题，除了作为第一个问题的应用给出的结果之外，我们在国内外已有结果的基础上研究了范围更大的图类，并得到了一些结果，鉴于讨论的情况和反例图较多，目前还在整理和修改阶段。