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].