The Research About The Problem Of Disjoint-Cycle And 2-Factor

More than two hundred years ago, the development of graph theory was inspired. The earliest known paper is due to Euler(1736) about the seven bridges of K-nigsberg. Since then, graph theory has developed very fast and numerous results on graph theory sprung forth. There are many nice and celeberted problems in graph theory, such as Hamiltonian problem, four-color problem, chinese postman problem, etc. Moreover, graph theory is widely applied in chemistry, computer science, biology and other disciplines. As a subfield in discrete mathematics, graph theory has attracted much attention from all perspectives.All graphs considered in this paper are finite, simple, undirected graphs with no loops and no multiple edges. The Hamiltonian cycle problem is one of the most well-konwn problems in graph theory. A cycle which contains every vertex of a graph is called a Hamiltonian cycle. Let G be a graph, k independent cycles of graph G are k cycles which have no common vertex in G . A 2-factor of G is a 2-regular spanning subgraph of G . Clearly, each component of a 2-factor of G is a cycle, and a Hamiltonian cycle is a 2-factor with exactly one component. The theory of independent cycles and 2-factor of graphs is the extending of the Hamilton cycle theory. It is an interesting problem in graph theory. Furthermore, it has important applications to computer science and networks.By means of classification discussion, arborescence and the fundamentals of putting on and taking off, this paper mainly focuses on the following three aspects in the general simple graph and the balanced bipartite graph: graphs containing specified number of independent cycles and 2-factor, independent cycles and 2-factor containing specified length, and graphs containing independent cycles and 2-factor which have specified properties. It is divided into three chapters. In Chapter 1, We introduce some basic concept and notations, the history of the cycle theory and main results. In Chapter 2 , utilizing some properties of the bipartite graph, the paper studies the problem about independent cycles and 2-factor in the balanced bipartite graph. For a 2-factor with k + 1 independent cycles, under certain degree conditions, that the 2-factor at least contains s 4-cycles and each cycle of s 4-cycles just contains two specifed edges are proved. Besides, the minimum degree condition for a bipartite graph just containing s 4-cycles and k - s 6-cycles is given for any containing specified vertices k independent cycles. In the last chapter, this paper discusses the problem about independent cycles and 2-factor in a simple graph. Firstly, the minimum degree condition for a simple graph just containing s K 3 and k - s K 4 is given for any k independent cycles,. Secondly, for a 2-factor with k + 1 independent cycles, under certain minimum degree conditions, that the 2-factor just contains s 3-cycles and k - s 4-cycles is proved.