Gutin, Gregory and Yeo, Anders (2000) Kings in semicomplete multipartite digraphs. Journal of Graph Theory, 33 (3).
Full text access: Open
A digraph obtained by replacing each edge of a complete p-partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called 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 that every vertex in D can be reached from q by a path of length at most r. Strengthening a theorem by K. M. Koh and B. P. Tan (Discr Math 147 (1995), 171-183) on the number of 4-kings in multipartite tournaments, we characterize semicomplete multipartite digraphs, which have exactly k 4-kings for every k = 1, 2, 3, 4, 5.
This is a Submitted version This version's date is: 2000 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/58ff7370-4d30-892c-eaf5-b6601cc1cbac/8/
Deposited by Research Information System (atira) on 18-Nov-2014 in Royal Holloway Research Online.Last modified on 18-Nov-2014