Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.disc.2006.04.023
Title: | On the 3-kings and 4-kings in multipartite tournaments | Authors: | Tan, B.P. | Keywords: | Distances Kings Multipartite tournaments |
Issue Date: | 6-Nov-2006 | Citation: | Tan, B.P. (2006-11-06). On the 3-kings and 4-kings in multipartite tournaments. Discrete Mathematics 306 (21) : 2702-2710. ScholarBank@NUS Repository. https://doi.org/10.1016/j.disc.2006.04.023 | 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. | Source Title: | Discrete Mathematics | URI: | http://scholarbank.nus.edu.sg/handle/10635/103765 | ISSN: | 0012365X | DOI: | 10.1016/j.disc.2006.04.023 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.