Tournament-like Digraphs

A digraph is semicomplete, if any two vertices of V(D) are adjacent. A semicomplete digraph without2-cycle is a tournament. Tournament are without doubt the important studied class of digraphs and they have been intensively studied. In1990, Bang-Jensen first introduced locally semicomplete digraphs. A digraph D is a locally semicomplete digraph, if for any x E V(D), D(N+(x)) and D(N-(x)) are both semicomplete. In1993, Bang-Jensen introduced are-locally semicompete digraphs. A digraph D is an arc-locally semicomplete digraph, if for any two adjacent vertices x,y of V(D), the in-neighbor u of x and the in-neighbor v of y are adjacent or u＝v, and the out-neighbor w of x and the out-neighbor z of y are both adjacent or w＝z. In1995, Bang-Jensen and Huang introduced quasi-transitive digraphs. In2004, Bang-Jensen introduced3-quasi-transitive digraphs. In2011. Hernandez-Cruz introduced k-(quasi)-transitive digraphs. A digraph is a k-(quasi)-transitive digraphs, if for any a path x0x1…Xk of length kin D,(x0and Xk. are adjacent) x0→Xk.If k＝2, then we call a2-quasi-transitive digraph as a quasi-transitive digraph.This thesis consists of four chapters. In Chapter1, we introduce some general con-cepts on graphs and digraphs and the arrangement of the paper.In Chapter2, we study kings in tournaments and locally scmicomplete digraphs. In Section2.1, we review some known results on tournament-like digraphs. In Section2.2, we study k-kings in strong tournaments and prove that there exist at least k+1k-kings (k≥3) in tournaments and give the structure of tournaments which have exactly k+1k-kings. It is known that every tournament has a2-king and every tournament with no vertex of in-degree zero has at least three2-kings. In Section2.2, we also give the structure of tournaments which have exactly three2-kings.In Chapter3, we study arc-locally in-semicomplete digraphs. In2004, Bang-Jensen studied strong arc-locally semicomplete digraphs and gave the structure of strong arc-locally semicomplete digraphs and proved that D is Hamitonian if and only if D is strong and has a cycle factor. We can use another method to give the definition of arc-locally semicomplete digraphs. Digraphs H1,H2,H3,H4are defined in Chapter1. A digraph is arc-locally semicomplete if it contains no induced subdigraphs H1and H2. In this thesis, we define that a digraph is arc-locally in-semicomplete if it contains no induced subdigraph H1; a digraph is arc-locally out-semicomplete if it contains no induced subdigraph H2; a digraph is arc-quasi-transitive if it contains no induced subdigraph H3; a digraph is3antipath-quasi-transitive if it contains no induced subdigraph H4. Galeana-Sanchez defined that a digraph is a3-quasi-transitive digraph if it contains no induced subdigraph H3. In this thesis, we use the concept of3-quasi-transitive digraphs rather than arc-quasi-transitive digraphs.Bang-Jensen conjectured that an arc-locally in-semicomplete digraph D is Hamilto-nian if and only if D is strong and has a cycle factor. Laborde, Payan and Xuong con-jectured that in every digraph, there exists an independent set intersecting every longest path.In Section3.1, we review some known results on arc-locally semicomplete digraphs. In Section3.2, we give the structure of strong arc-locally in-semicomplete digraphs and prove that Bang-Jensen's conjecture is true. In Section3.3, we give the structure of non-strong arc-locally in-semicomplete digraphs and prove that Laborde et al's conjecture for arc-locally in-semicomplete digraphs is true.In Chapter4, we study k-quasi-transitive digraphs. In Section4.1, we review some known results on k-(quasi)-transitive digraphs. In Section4.2, we give the structure of non-strong3-quasi-transitive digraphs. In Section4.3, we prove that Laborde et al's conjecture for3-quasi-transitive digraphs is true. Hernandez-Cruz conjectured:Let D be a3-quasi-transitive digraph. Then the underlying graph of D, UG(D), admits a3-transitive orientation. In Section4.4, we prove that the conjecture is true. In Section4.5, we prove that there exists at least one4-king in3-quasi-transitive digraphs. Hernandez-Cruz conjectured:Let k-1be a prime and D be a strong k-transitive digraph. If|V(D)|≥k+1,D contains an n-cycle, with n≥k and (n, k-1)=1, and D is not a symmetrical (k+1)-cycle, then D is a complete digraph. In Section4.6, we prove that the conjecture is true.