Kings in semicomplete multipartite digraphs

A digraph obtained by replacing each edge of a complete p-partite graph by an are or a pair of mutually opposite arcs with the same end vertices is ca lled a semicomplete p-partite digraph, or just a semicomplete multipartite digraph. A semicomplete multipartite digraph with no cycle of length two is a multipartite tournament. In a digraph D, an r-king is a vertex q such th at every vertex in D can be reached from q by a path of length at most r. S trengthening a theorem by K. M. Koh and B. P. Tan (Discr Math 147 (1995), 1 71-183) on the number of 4-kings in multipartite tournaments, we characteri ze semicomplete multipartite I digraphs, which have exactly k 4-kings for e very k = 1, 2, 3, 4, 5. (C) 2000 John Wiley & Sons, Inc.