Vertex-disjoint Cycles And The Second Out-neighbourhood For Local Tournaments

As a special class of digraphs,tournaments naturally become one of the primary topics related to digraphs.As the concept and a classification of locally semicomplete digraphs were proposed(especially local tournaments are locally semicomplete digraphs with no 2-cycle),as a generalization of tournaments,local tournaments become one of the main research top-ics after the tournaments.Researchers often continue to consider some problems in local tournaments that have been solved in tournaments.Problems on circles and the second neighbourhood are widely concerned by researchers.In this paper,we investigate the follow-ing problems on circles and the second neighbourhood in local tournaments that have been solved in tournaments:In 1981,Bermond and Thomassen stated the conjecture:for any position integer r,any digraph with minimum out-degree at least 2r-1 contains at least r vertex-disjoint cycles.In 1990,Seymour stated the conjecture:every oriented graph has a vertex whose second out-neighbourhood is at least as large as its out-neighbourhood.In 2006,Sullivan stated the conjectures:(1)every oriented graph has a vertex whose second out-neighbourhood is at least as large as its in-neighbourhood.(2)every oriented graph has a vertex that satisfies the sum of the number of second out-neighbourhood and the number of out-neighbourhood is not less than twice the number of in-neighbourhood.In particular,we study Lichiardopol’s conjecture in tournaments:for any integers q≥ 3 and r≥ 1,any tournament T with minimum out-degree at least(q-1)r-1 contains at least r vertex-disjoint q-cycles.Both Bermond-Thomassen s conjecture and Lichiardopol s conjecture are related to circles,so in this paper,we mainly investigate vertex-disjoint cycles,Seymour’s conjecture,Sullivan’s conjectures in local tournaments and this paper is divided into four chapters.In Chapter 1 is the preface.Basic concepts of digraphs,definitions and structures of local tournaments are introduced.And arrangement of article content is given.In Chapter 2,we consider the Bermond-Thomassen’s conjecture in local tournaments and obtain:(a)The Bermond-Thomassen’s conjecture is true for local tournaments,i.e.,for any position integer r,every local tournament with minimum out-degree at least 2r-1 contains at least r vertex-disjoint cycles.On Lichiardopol’s conjecture in tournaments,we can get the following conclusion:(b)Lichiardopol’s conjecture is true when r ≤3,i.e.,for any position integer r,q≥ 3,every tournament with minimum out-degree at least(q-1)r-1 contains at least r vertex-disjoint q-cycles when r ≤3.In Chapter 3,we research the Seymour conjecture in local tournaments.For conve-nience,the vertex satisfying the Seymour conjecture is called a Seymour vertex.We obtain:(a)Every round decomposable local tournament D has one Seymour vertex.(b)Every round decomposable local tournament D with no vertex of out-degree zero has at least two Seymour vertices.(c)For non-round decomposable local tournament D with δ+(D)=a,there exists a vertex v∈V(D)such that d++(v)≥γd+(v),where γ=min{3/4+1/2a,(?)}In Chapter 4,we research the Sullivan conjectures in local tournaments.For conve-nience,the vertex satisfying the Sullivan conjecture(i)is called a Sullivan-i vertex,where i ∈ {1,2}.We obtain:(a)Every local tournament D has a Sullivan-i vertex for i ∈ {1,2}.(b)Every local tournament D with no vertex of in-degree zero has at least two Sullivan-1 vertices.(c)Every round decomposable local tournament D with no vertex of in-degree zero has at least two Sullivan-2 vertices.(d)Every non-round decomposable local tournament D that is not a tournament either has at least two Sullivan-2 vertices or has a Sullivan-2 vertex v satisfying d++(v)+d+(v)≥2d-(v)+2.