A Constructive Solution to a Tournament Problem

Abstract

By a tournament T n on n vertices , we shall mean a directed graph on n vertices for which every pair of distinct vertices form the endpoints of exactly one directed edge (e.g., see [5]). If x and y are vertices of T n we say that x dominates y if the edge between x and y is directed from x to y . In 1962, K. Schütte [2] raised the following question: Given k > 0, is there a tournament T n(k) such that for any set S of k vertices of T n(k) there is a vertex y which dominates all k elements of S . (Such a tournament will be said to have property P k .)