Embedding and Partition of Graphs

点击翻译按钮获取中文摘要

(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.