کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651216 | 1342527 | 2006 | 9 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 306, Issue 21, 6 November 2006, Pages 2702–2710