Vertex-Disjoint Cycles In Graphs

In this thesis, we mainly discuss the number of vertex-disjoint cycles. We say two cycles are independent if the two cycles has no common vertices. Let l, k and n be three positive integers such that l is odd and n-sk+1 is even where We define a set Fl,k,n of graphs as follows. A graph G belongs to Fl,k,n if and only if V(G) has a partition (X, Y, Z) with such that Y and Z are two vertex-disjoint sets. The edges between Y and Z are vertex-disjoint edges, there are no edges between X and Z and every vertex in X is adjacent to every vertex in Y. There is no restriction to edges among vertices in X.In this thesis, we consider the number of disjoint cycles problems, this is an important problem and play an important role in graph theory. Many scholars studied it. Hong Wang proved the following result in [22]:(1) Let G be a connected graph of order at least 3k, where k is a positive integer. Suppose that for every pair of vertices x and y of distance 2 in G. If G contains k cycles C1, C2…,Ck and there is no cycles in There exists a path of order s> 4 in Then G contains k vertex-disjoint cycles or n is odd and G belongs to F3,k,n-In this thesis, we proved the following result:(2) Let G be a connected graph of order at least 3k, where k is a positive integer. Suppose that for every pair of vertices x and y of distance 2 in G. If G contains k cycles C1, C2…, Ck and there is no cycles in There exists a path of order s≤4 in Then G contains k vertex-disjoint cycles or n is odd and G belongs to F3,k,n.By the above results, we can obtain: Let G be a connected graph of order at least 3k, where k is a positive integer. Suppose that for every pair of vertices x and y of distance 2 in G. Then G contains k vertex-disjoint cycles or n is odd and G belongs to F3,k,n.Lu-shun Ding proved the following result in [11]:(1) Let G be a 2-connected K1,3-free graph of order n=| V(G)|≥51 and for each pair of non-adjacent vertices x and y, Then for each k with one of the following must hold:(1)G has a 2-factor with exactly k components;(2)G contains k cycles C1, C2,…, Ck and a subgraph H which is complete, s.t.By the proof of the above result, if there exists a vertex v in with then (1) holds. If for each vertex v in with then (2) holds.In this thesis, we proved the following result:(2) Let G be a 2-connected K1,3-free graph with order n≥68. If then for each If G contains k cycles C1,C2 …,Ck and for each vertex v in with then G contains exactly k cycles C1, C2…,Ck such that has at most one vertex v withBy the above results, we can obtain: Let G be a 2-connected K1,3-free graph with order n≥68. If then for each , G contains exactly k cycles C1, C2…, Ck such that has at most one vertex v withFor disjoint triangles in a graph, we obtain the following result: Let G be a K1,3-free graph with order n and k≥1 be an integer. If n> 3k+3 and σ2(G)≥2k+2 and △(G)> 3, then G contains k disjoint triangles.