Some Results For Vertex-disjoint Subgraphs In Graphs

Graph theory is a mathematics branch with a long history and has developed rapidly in recent years. It is a subfieled in Combinatorial mathematics. In 1736, Euler published the first article of graph theory to solve the famous problem of seven Bridges of konigsberg. From the middle of the 19th century, graph the-ory into the second stage of development. During this period, a large number of problems of graph theory have emerged, such as the map colored four-color problem, developed from " around the world " game of Hamilton issues. In the 20th century, with the development of computer science, the extenive application in many filed draw more and more attention from mathamatics field and other science field.All graphs in this paper are considered only simple, finite, undirected graphs with no multiple edges and no loops. Let G be a graph, x and y are distinct vertices in G. A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. A tree is an acyclic connected graph. A spanning tree is a graph which contains all veitices of G and this graph is a tree. Let T1 and T2 are two spanning trees of a graph G, if, for any two vertices x, y of G, the x-y path in T1 and T2 are internally, then T1 and T2 are two completely independent spanning trees of G. A hamiltonion cycles is a cycle which contains every vertex of G. In this paper, we mainly consider about the following problem:degee sum condition for two completely independent spanning trees, the extremal function for three disjoint theta graphs.This paper is divided into four chapters. In chapter 1, we introduce some notations and terminology, the history and the progress of the problem of we study.In chapter 2, we consider the extremal function for three disjoint theta graphs. The main result is as following:every graph of order n≥12 and size at least max{[(3n+79)/2], [(11n-33)/2]} contains three disjoint theta graphs.In chapter 3, we conider the degee sum condition for two completely independent spanning trees. The main result is as following:a graph of order n≥7 has two completely independent spanning trees, if the degree sum of any two non-adjacent vertices in this graph is at least n.Furthermore, in the end of every chapters, we list some problems for future research and discussions.