Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 177-183 |
| Number of pages | 7 |
| Journal | Journal of Graph Theory |
| Volume | 33 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Mar 2000 |
| Externally published | Yes |
Keywords
- Distances
- Kings
- Multipartite tournaments
- Semicomplete multipartite digraphs
ASJC Scopus subject areas
- Geometry and Topology