To Figure

This thesis contributes to directed cycles in digraphs, including the relations between the girth g(D) (length of the shortest directed cycle) of D and degrees of vertices of D and between the shortest directed cycle of D and the binding number of D, among which vertex-transitive digraphs are studied in detail. This thesis is motivated by the following two related conjectures on digraphs.Caccetta-Haggkvist Conjecture Let D be a digraph with δ+{D) > d. Theng(D)<[n/d].Seymour's Second Outdegree Conjecture In any simple digraph D, there is at least one vertex v ∈ V(D) such that \N++(v)\ > \N+(v)\.In Chapter 1, the terminology and notations on graph theory are introduced, and then a brief introduction to the study contents and main results obtained in this thesis is given.In chapter 2, a summary on the development of the above two conjectures is given, in which the special case of Caccetta-Haggkvist Conjecture, i.e., d > n/3, is described particularly. And some Conjectures that are equivalent to the Caccetta-Haggkvist Conjecture and its special case are given. It is proved that Seymour's Second Out-degree Conjecture holds if and only if it holds for strong connected digraphs.In chapter 3, vertex-transitive digraphs are studied, which are very important in both theory and application. Many results on undirected vertex-transitive graphs are applied on directed cases in parallel. And some different conclusions from undirected case are obtained. It is proved that the above two Conjectures hold for vertex-digraphs. Connectivity is discussed particularly, and some new conceptions are Proposed, such as atom matching, atom-contracted digraph and atom stabilizer subgroup, based on which the structure characteristic of vertex-transitive digraphs is analyzed further, and current connectivity theory on vertex-transitive digraphs is consummated. Particularly, explicit expression for connectivity of Cayley digraphs is given, Doom and Meng's results are also generalized and improved. At last, Cayley digraphs with optimal connectivity are analyzed.In chapter 4, the conception of binding number of undirected graphs is introduced to digraphs, based on which the relationship between degree condition of vertices and girth is generalized to the relationship between neighborhood condition of vertices sets and girth. The properties of binding number are discussed, the value scope of binding number is obtained, and the existence of digraphs with a given binding number is proved. Two Conjectures on the relationship between binding number and girth are proposed. Also, the binding numbers of some special digraphs are computed and the relationship between binding number and connectivity is analyzed.At the end of the thesis, we give an overview of the whole contents of the thesis and also propose some problems for further research.