Kings in multipartite tournaments
type: Item
instance of: scholarly article
title: Kings in multipartite tournaments
zbMATH Open document ID: 0841.05038
DOI: 10.1016/0012-365X(94)00169-J
author: B. P. Tan
author: K. M. Koh
published in: Discrete Mathematics
publication date: 1996-03-24T00:00:00Z
review text: 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.
reviewed by: G. Gutin
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 858056
zbMATH Keywords: king
zbMATH Keywords: digraph
zbMATH Keywords: tournament
MaRDI profile type: Publication
cites work: Q3346349
cites work: On multipartite tournaments
cites work: The radii of n-partite tournaments
cites work: Kings in bipartite tournaments
cites work: Kings in \(k\)-partite tournaments
cites work: Every vertex a king
full work available at URL: 0012-365x(94)00169-j
OpenAlex ID: W1998739158
description: scientific article; zbMATH DE number 858056