Embedding and Partition of Graphs

(1)In 1997年，Brandt等人证明了一个阶至少为4k且不相邻点的度和至少|V（G）|可以被划分为k个不相交的循环。这一结果在几个方面得到推广。我们弱化了度和假设，|V（G）|-k+1通过允许退化的循环（边缘和孤立的顶点）。我们还得到了最小度的充分条件，以确保每个循环通过一个指定的顶点。我们还解决了每个循环通过指定顶点或指定边的问题。此外，我们解决了二部图的问题。（2）Erdos-Chvatal定理：如果图的独立数不大于连通数，则该图包含一个Hamilton圈。我们把这个结果推广到长圈的存在性。(3)We研究了不含k个不相交圈且独立数至多为α的图的最大阶. (4)We证明了如果G是（mg+m-1，mf-m+1）-图，且对G的任意顶点x，k ∈ g（x）∈ f（x），则G可分解为（g，f）-因子，其中每个因子包含k条指定边.

(1)In 1997, Brandt and others proved that a graph G of order at least 4k and the degree sum of nonadjacent vertices at least |V(G)| can be partitioned into k disjoint cycles. This result is generalized in several ways. We weakened the degree sum assumption to |V(G)|-k+1 by allowing degenerated cycles (edges and isolated vertices). We also obtained sufficient conditions on the minimum degree to assure that each cycle passes through a specified vertex. We also solved the problem in which each cycle passes through a specified vertex or a specified edge. Furthermore, we solved the problem for bipartite graphs.(2)Erdos-Chvatal theorem says that if the independence number is not larger than the connectivity, the graph contains a Hamiltonian cycle. We generalized this result to the existence of a long cycle.(3)We investigated the maximum order of a graph without k disjoint cycles and the independence number is at most α.(4)We proved that if G is an (mg+m-1,mf-m+1)-graph and if k≦g(x)≦f(x) for any vertex x of G,G can be factorized into (g,f)-factors in which each factor contains k specified edges.