## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  117.17402
Autor:  Erdös, Pál
Title:  On a problem in graph theory (In English)
Source:  Math. Gaz. 47, 220-223 (1963).
Review:  Let f(k) be the minimum number of vertices in a complete graph which can be so oriented that, for every set S of k vertices, there is a vertex x joined to all elements of S by edges directed from x to S. The author proves that f(k) \geq 2k+1-1 and limsup 2-k k-2 f(k) \leq log 2.
Reviewer:  C.St.J.A.Nash-Williams
Classif.:  * 05C35 Extremal problems (graph theory)
Index Words:  topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag