Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 277.05135
Autor: Bollobás, Béla; Erdös, Paul
Title: On the structure of edge graphs. (In English)
Source: Bull. Lond. Math. Soc. 5, 317-321 (1973).
Review: Let Kr(t) be a graph with r groups of t vertices, each two vertices of which are connected iff they belong to different groups. denote g(n,r, \epsilon) the minimal such t that any graph with n vertices and m = [((r-2)/2(r-1)+\epsilon)n2] edges contains a Kr(t), (\epsilon > 0). In this article it is proved that for any r and 0 < \epsilon < {1 over 2}(r-1) there exist constants c1,c2 such that c1 log n \leq g(n,r, \epsilon) \leq c2 log n for sufficiently large n and c2 ––> 0 if \epsilon ––> 0.
Reviewer: St.Znám
Classif.: * 05C35 Extremal problems (graph theory)
05C99 Graph theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag