Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T17:38:22.751Z Has data issue: false hasContentIssue false
  • English
  • Français

A Constructive Solution to a Tournament Problem

Published online by Cambridge University Press:  20 November 2018

R. L. Graham  and
J. H. Spencer
R. L. Graham
Affiliation:
Bell Telephone Laboratories Inc., Murray Hill, New Jersey
J. H. Spencer
Affiliation:
The Rand Corporation, Santa Monica, California
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

By a tournament Tn 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 Tn 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 Tn(k) such that for any set S of k vertices of Tn(k) there is a vertex y which dominates all k elements of S. (Such a tournament will be said to have property Pk.)

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 14 , Issue 1 , January 1971 , pp. 45 - 48
Copyright
Copyright © Canadian Mathematical Society 1971

References

1. Burgess, D. A., On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179-192.Google Scholar
2. Erdös, P., Applications of probability to combinatorial problems, Proc. of Colloq. on Combinatorial Methods in Probability Theory, August 1–10 (1962), 90-92.Google Scholar
3. On a problem in graph theory, Math. Gaz. 47 (1963), 220-223.Google Scholar
4. LeVeque, W. J., Topics in number theory, Vol. I, Addison-Wesley, Reading, Mass., 1954.Google Scholar
4?C.M.B. Google Scholar
5. Moon, J. W., Topics on tournaments, Holt, New York, 1968.Google Scholar
6. Szekeres, E. and Szekeres, G., On a problem of Schütte and Erdös, Math. Gaz. 49 (1965), 290-293.Google Scholar