Kings in multipartite tournaments (Q1910515): Difference between revisions

A vertex \(x\) in a digraph \(D\) is a \(k\)-king if the distance from \(x\) to any other vertex of \(D\) is at most \(k\). A multipartite tournament is an orientation of a complete multipartite graph. The reviewer [Math. Notes 40, 743-744 (1986; Zbl 0691.05016); translation from Mat. Zametki 40, No. 3, 414-417 (1986)] and, independently, \textit{V. Petrovic} and \textit{C. Thomassen} [Discrete Math. 98, No. 3, 237-238 (1991; Zbl 0751.05047)] proved that a multipartite tournament \(T\) has a \(k\)-king for some finite \(k\) iff \(T\) contains at most one vertex of indegree zero. Moreover, if \(T\) contains at most one vertex of indegree zero, then \(T\) has a 4-king. In this paper, the following is proved: if \(T\) is an \(m\)-partite tournament without vertices of indegree zero, then \(T\) has at least four 4-kings when \(m= 2\) and three 4-kings when \(m\geq 3\). The extremal multipartite tournaments are characterized.