Some Topics On Cycles Of Oriented Graphs

In recent years,the studies of oriented cycles in digraphs have attracted a lot of attentiongs.In 1978,Caccetta and Haggkvist proposed a conjecture regarding the precise degree which forces an oriented cycle:An oriented graph on n vertices with minimum outdegree d contains a cycle of length at most[n/d].This conjecture is one of the important conjecture in Graph Theory,and has not been solved.A directed graph G is an ordered pair(V(G),E(G),?)consisting of a set V(G)of vertices set E(G),disjoint from V(G),of arcs,together with an incidence function ? that associates with each arc of G an ordered pair of(not necessarily distinct)vertices of G.A digraph is an oriented graph if it is an orientation of a simple graph.We write ?+(G)= min{dG+(v)|v ? V(G)} for its minimum outdegree and ?-(G)= min{dG-(v)|v ? V(G)} for its minimum indegree.We write ?0(G)= min{?+(G),?-(G)} for its minimum semidegree.Kelly,Kuhn and Osthus showed that for each l>4 every sufficiently large oriented graph G with ?0(G)>[n/3]+ 1 contains an l-cycle.Moreover,for any vertex u ? V(G))there is an l-cycle containing u.Meanwhile,they proposed a conjecture regarding the precise minimum semidegree which forces an/-cycle with some restrictions on l:Let l? 4 be a positive integer and let k be the smallest integer that is greater than 2 and does not divide l.Then there exists an integer n0 = n0(l)such that every oriented graph G on n?no vertices with minimum semidegree ?0(G)>[n/k]+ 1 contains an l-cycle.In this thesis,we mainly discuss the cycles in oriented graphs.We construct our work in four chapters and our main results will be proved in the second and third chapter.In Chapter 1,we introduce some basic definitions and notations about the oriented graphs,the background and development of the research,and the main results of our thesis.In Chapter 2,we mainly consider the cycles in oriented graphs which con-tains no directed triangle.Suppose that 0<e<1,? ? 0.3014 are reals,and G is a triangle-free oriented graph on vertices with ?0(G)?(?+?)n.Then each vertex of G can be contained in an l-cycle for each 4?<?n/(1-?)+ 2.In Chapter 3,we mainly deal with long cycles of sufficiently large oriented graphs.Let l>7.332 x 107 and l is not divided by 7.We prove that:for all?>0 there exists an integer n1 = n1(?,l)such that every oriented graph G on n?n1 vertices with minimum semidegree ?0(G)>(1 + ?)n/7 contains an l-cycle.In Chapter 4,we introduce some progresses about the Caccetta-Haggkvist conjecture,and proved that every triangle-free oriented graph G on n vertices with ?0(G)>n/5 + l contains a 4-cycle.