The Transitivity Of Tournaments And The 3-kings-of-kings In Semicomplete Multipartite Digraphs

The main contents of this thesis involve two aspects of digraphs: the transitivity of multipartite tournaments and the 3— kings-of-kings in semicomplete multipartite digraphs.n— partite tournament is an orientation of a complete n— partite graph. When n = 2, it is a bipartite tournament. A tournament is an n— partite tournament that contain just n vertices. A digraph D is transitive if, for every pair of arcs xy and yz in D such that x ≠y, the arc xz is also in D.In [1], Jorgen. Bang-Jensen, Gregory Gutin proved that if D is a digraph with an acyclic ordering D₁, D₂, … D_p of its strong components. If the digraph D is transitive ,then each of D_i is complete, and the digraph H obtained from D by contraction of D₁, D₂, … D_p followed by delection of multiple arcs is a transitive oriented graph. In other words D = H[D₁,D₂,…D_p]. Based on the above, we study the transitivity of tournaments,bipartite and multipartite tournaments, and give the sufficient and necessary conditions of then in Chapter 2.From 1953 to now, about the king of tournaments and multipartite tournaments, there have been rather abundant results. In 1980, Maurer introduced the conception of kings-of-kings in tournaments. It is:Let H₁ be a tournament, and let K₂(H₁) be the set of 2— kings of H₁. For i ≥ 1, let H_i+1 = H_i[K₂(H_i)]. Observe that K₂(H₁), K₂(H₂),… is a descending chain of subsets of K₂(H₁). Since K₂(H₁) is a finit set, there exists an integer p, such that for all i 2(H_i+1) (?) K₂(H_i), and for all i ≥ p, K₂(H_i+1) = K₂(H_i). Maurer called any vertex u ∈ K₂(H_p) a king-of-kings.Fowlling Maurer, B.P.Tan investigates the r— kings-of-kings in semicomplete multipartite digraphs with no transmiters for r = 1,2,3,4.He proves that:when r = 1, we can not define 1— kings-of-kings in semicomplete multipartite digraphs with no transmitters.when r = 2,4, The set of r— kings-of-kings in semicomplete multipartite digraphs with no transmitters is not empty.when r = 3, The set of r— kings-of-kings in semicomplete multipartite digraphs with no transmitters may be empty. Then he raises the following problem:Determine those semicomplete multipartite digraphs with no transmitters such that the set of 3— kings-of-kings is non empty.And he says that : to solve the problem,we just need consider those semicomplete multipartite digraphs T with no transmitters such that K^iT) > 1. In Chapter 3 of this thesis, we solve the problems as follows:(1) give out some sufficient conditions for regular semicomplete multipartite digraphs T with no transmitters.(2) give out some semicomplete multipartite digraphs with no transmitters such that the set of 3— kings-of-kings is non empty.