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