Componentwise Complementary Cycles And Complementary Cycles In Multipartite Tournaments

As it is well known, the class of tournaments has a very rich theory and it is the most well-studied class of digraphs (see [47] 1966 and the survey articles [48], [49] 1978, [50] 1981, [51] 1994, and [52] 1996 etc). So, the study of its generalizations has also received much interest recently (see e.g. Volkmann [15] and [16]).In 1990 Bang-Jensen introduced a very interesting generalization of tournaments the class of locally semicomplete digraphs. A digraph is semicomplete if for any two distinct vertices, there is at least one arc between them. A digraph is locally semicomplete if for every vertex x, the set of in-neighbours as well as the set of out-neighbours of x induce semicomplete digraphs. A local tournament is a locally semicomplete digraph without a directed cycle of length 2.Another interesting generalization of tournaments is the class of so-called semicomplete multipartite digraphs. A digraph obtained by replacing each edge of a complete n-partite graph with an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete n-partite digraph or a semicomplete multipartite digraph. A multipartite tournament is a semicomplete multipartite digraph without a cycle of length two. It is clear that a tournament is a multipartite tournament, each of whose partite set contains exactly one vertex.It is obvious that two classes of locally semicomplete digraphs and semicomplete multipartite digraphs are bigger than that of tournaments.A digraph D is cycle complementary if there exist two vertex-disjoint cycles C and C' such that V(D) = V(C)∪V(C'). Thereinto, C and C' are said to be a pair of complementary cycles of D.The statement on the existence of complementary cycles depends on how much a multipartite tournament differs from being regular. Hence, we use two parameters introduced by Yeo. He defines the local irregularity as and the global irregularityIt is clear that i_l(D)≤i_g(D).If i_g(D) = 0, then D is regular, and if i_g(D)≤1 , then D is called almost regular. If i_l(D)≤1 , then D is called locally almost regular.The problem of complementary cycles in tournaments was almost completely solved by Reid in 1985 and by Song in 1993. These authors proved that every 2-connected tournament D on at least 8 vertices has complementary cycles of length t and |V(D)| - t for all t∈{3,4,…,|V(D)| - 3}. Some years later, Guo and Volkmann extended this result to locally semicomplete digraphs. In addition, there are some results on complementary cycles in bipartite tournaments by Z. Song, K. Zhang, Manoussakis, and J. Wang. 2004, Volkmann confirmed that each regular multipartite tournament is cycle complementary, unless it is a member of a finite family of regular multipartite tournaments. However, the problem about the existence of complementary cycles in multipartite digraphs which are neither tournaments and bipartite tournaments nor locally semicomplete digraphs and regular digraphs is still open. It seems to be quitely difficult. So, we give new the definition of componentwise complementary cycles at first, which is defined as follows:Definition Let V₁,V₂,…,V_c be the partite sets of digraph D. If there exist two vertex disjoint cycles C and C' in D such that V_i∩(V(C)∪V(C'))≠(?) for all i = 1,2,…,c, then C and C' are said to be a pair of componentwise complementary cycles of D.If a digraph D contains two componentwise complementary cycles, then D is cycle componentwise complementary.In this thesis we will mainly examine the existences of componentwise complementary cycles and complementary cycles in multipartite tournaments. It is divided into five chapters.The thesis starts with a short introduction.In Chapter 2, for the first time, we give new definition of componentwise complementary cycles, by the definition, a pair of complementary cycles is a pair of componentwise complementary cycles, so this definition has important sense. The same time, for the first time, we prove the existence of componentwise complementary cycles in some classes of multipartite tournaments and obtain the following important results:Firstly, we try to examine the existence of componentwise complementary cycles in 2-strong multipartite tournaments. Note that every 2-strong multipartite tournament contains a 3-cycle. Let C be a 3-cycle of multipartite tournament D. If D—V(C) is strong, then D—V(C) contains a longest cycle C' such that C and C' are two componentwise complementary cycles of D. We main prove the existence of componentwise complementary cycles when D—V(C) is nonstrong?Conclusion 1 Let D be a 2-strong n-partite tournament that is not a tournament, where n≥6, C be a 3-cycle of D and D—V(C) be nonstrong. For the unique acyclic sequence D₁,D₂,…,D_αof D—V(C), whereα≥2, if there is only some one D_i containing cycles and the others consist of a single vertex, where 1 < i <α, then D contains a pair of componentwise complementary cycles.Conclusion 2 Let D be a 2-strong n-partite tournament that is not a tournament, where n≥6, C be a 3-cycle of D and D—V(C) be nonstrong. For the unique acyclic sequence D₁, D₂,…,D_αof D—V(C), whereα≥2, if |V(D_α+1-i)| = 1, D_i contains cycles for i = 1 or i =α, and the others consist of a single vertex, then D contains a pair of componentwise complementary cycles.Conclusion 3 Let D be a 2-strong n-partite tournament that is not a tournament, where n≥6, C be a 3-cycle of D and D—V(C) be nonstrong. For the unique acyclic sequence D₁,D₂,…, D_αof D—V(C), if D₁ and D_αcontain cycles and the others consist of a single vertex, then D contains a pair of componentwise complementary cycles.Combining Conclusion 1, Conclusion 2, and Conclusion 3, we have the following conclusion.Conclusion 4 Let D be a 2-strong n(n≥6)-partite tournament that is not a tournament, C be a 3-cycle of D and D—V(C) be nonstrong. For the unique acyclic sequence D₁,D₂,…, D_αof D—V(C), whereα≥2, let D_c = {D_i|D_i contains cycles, i = 1,2,…,α} and D_c = {D₁, D₂ ,…, D_α} \ D_c. If D_c≠(?) and each element of D_c consists of a single vertex , then D contains a pair of componentwise complementary cycles.Secondly, we confirm the existence of componentwise complementary cycles in locally almost regular multipartite tournaments whose all partite sets have the same cardinality.Conclusion 5 Let D be a locally almost regular c-partite (c≥3) tournament with |V(D)|≥6. If all partite sets have the same cardinality, then D contains a pair of componentwise complementary cycles, unless D is isomorphic to T₇¹, D_3,2 (see Fig. 1.1, Fig. 1.3).Lastly, we consider the special case where the digraphs are almost regular 3-partite tournaments.Conclusion 6 If D be an almost regular 3-partite tournament with |V(D)|≥6, then D contains a pair of componentwise complementary cycles, unless D is isomorphic to D_3,2, sketched in Fig. 1.3.In the following, we obtain results on complementary cycles with fixed length in multipartite tournaments.In Chapter 3, we partially prove the conjecture given by Yeo in 1999 and obtain the following conclusion:Conclusion 7 A regular c-partite tournament D with c≥5 and |V(D)|≥8 has a pair of vertex disjoint cycles of length 5 and | V(D)|—5.It is possessed of certain effect for completely solving Yeo's conjecture. In Chapter 4, for the first time, we extend the problem of complementary cycles of regular multipartite tournaments to multipartite tournaments which are not regular and obtain a important result by which we can get a lot of important results.Conclusion 8 Let D be a locally almost regular c-partite (c≥3) tournament with |V(D)|≥6. If V₁, V₂,…, V_c are the partite sets of D and |V₁| =|V₂| =…= |V_c|, then D contains a pair of vertex disjoint cycles of length 3 and | V(D)|—3, unless D is a member of a finite family of multipartite tournaments.This result leads to Conclusion 5 and the next corollaries hold since every regular multipartite tournament is a locally almost regular multipartite tournament whose partite sets have the same cardinality.Corollary 1(Volkmann [16]) If D is a regular 3-partite tournament with |V(D)|≥6, then D contains a pair of vertex disjoint cycles of length 3 and |V(D)| - 3, unless D is isomorphic to D_3,2 (see Fig. 1.3).Corollary 2(Volkmann [15]) If D is a regular c-partite (c≥4) tournament with |V(D)|≥6, then D contains a pair of vertex disjoint cycles of length 3 and |V(D)| - 3, unless D is isomorphic to T₇¹, D_4,2, D_4,2^* (see Fig. 1.1, Fig. 1.4, Fig. 1.5).The same time, we extend Yeo's conjecture to a general case and obtain two new conjectures.Conjecture Let D be a locally almost regular c-partite (c≥3) tournament with |V(D)|≥6. If V₁, V₂,…, V_c are the partite sets of D and |V₁| = |V₂| =…= |V_c|, then D contains a pair of vertex disjoint cycles of length t and |V(D)| - t, for all t∈{3,4,…, |V(D)| - 3}, unless D is a member of a finite family of multipartite tournaments.Conjecture If D is an almost regular c-partite (c≥3) tournament with |V(D)|≥6, then D contains a pair of complementary cycles, unless D is a member of a finite family of multipartite tournaments.We present some future problems in last chapter.