On the 3-kings and 4-kings in multipartite tournaments

Abstract

Koh and Tan gave a sufficient condition for a 3-partite tournament to have at least one 3-king in [K.M. Koh, B.P. Tan, Kings in multipartite tournaments, Discrete Math. 147 (1995) 171-183, Theorem 2]. In Theorem 1 of this paper, we extend this result to n-partite tournaments, where n ≥ 3. In [K.M. Koh, B.P. Tan, Number of 4-kings in bipartite tournaments with no 3-kings, Discrete Math. 154 (1996) 281-287, K.M. Koh, B.P. Tan, The number of kings in a multipartite tournament, Discrete Math. 167/168 (1997) 411-418] Koh and Tan showed that in any n-partite tournament with no transmitters and 3-kings, where n ≥ 2, the number of 4-kings is at least eight, and completely characterized all n-partite tournaments having exactly eight 4-kings and no 3-kings. Using Theorem 1, we strengthen substantially the above result for n ≥ 3. Motivated by the strengthened result, we further show that in any n-partite tournament T with no transmitters and 3-kings, where n ≥ 3, if there are r partite sets of T which contain 4-kings, where 3 ≤ r ≤ n, then the number of 4-kings in T is at least r + 8. An example is given to justify that the lower bound is sharp. © 2006 Elsevier B.V. All rights reserved.