Article ID Journal Published Year Pages File Type
4651216 Discrete Mathematics 2006 9 Pages PDF
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⩾3n⩾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⩾2n⩾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⩾3n⩾3. Motivated by the strengthened result, we further show that in any n-partite tournament T   with no transmitters and 3-kings, where n⩾3n⩾3, if there are r partite sets of T   which contain 4-kings, where 3⩽r⩽n3⩽r⩽n, then the number of 4-kings in T   is at least r+8r+8. An example is given to justify that the lower bound is sharp.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,