The Three Results Of Quasi-transitive Oriented Graphs

Tournaments are an important class of digraphs.There are many conclusions on tour-naments.In this thesis,for quasi-transitive oriented graphs as a superclass of tournaments,we obtain the number of Seymour vertices of quasi-transitive oriented graphs under the d-ifferent minimum out-degrees,give the number and the length of vertex-disjoint cycles in quasi-transitive oriented graphs and calculate the upper bound of diameter in quasi-transitive oriented graphs.This thesis is divided into four chapters.Chapter 1 contains the basic concepts of digraphs,definitions,structures and important conclusions of quasi-transitive oriented graphs.Also the arrangement of the content of paper was given here.Chapter 2 deals with the Seymour’s second neighbourhood conjecture for quasi-transitive oriented graphs and obtains:every quasi-transitive oriented graph D has at least one vertex with d+(v)≤d++(v);every quasi-transitive oriented graph D with no vertex of out-degree zero has at least two vertices with d+(v)≤d++(v).In chapter 3,we study the Bermond-Thomassen’s conjecture for quasi-transitive ori-ented graphs and obtain:for intergers k,every quasi-transitive oriented graph D withδ+(D)≥ 2k-1 contains at least k vertex-disjoint 3-cycles;for intergers k,every quasi-transitive digraph D with δ+(D)≥2k-1 contains at least k vertex-disjoint 2-cycles or 3-cycles.In chapter 4,we discuss the upper bound of diameter and the relationship with Caccetta-Haggkvist conjecture in quasi-transitive oriented graphs and obtain:every strong quasi-transitive oriented graph D with δ+(D)≥r satisfies diam(D)≤n-2r+1;every quasi-transitive oriented graph D with δ+(D)≥ r contains a directed cycle of length at most[n/r].