Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 495.05035
Autor: Babai, Laszlo; Chung, F.R.K.; Erdös, Paul; Graham, Ronald L.; Spencer, J.H.
Title: On graphs which contain all sparse graphs. (In English)
Source: Ann. Discrete Math. 12, 21-26 (1982).
Review: Let s(n) denote the maximum number of edges in a graph G which contains as subgraphs all graphs with n edges. The authors prove that for sufficiently large n cn2/ log2n < s(n) < c'n2 log log n/ log n (here c and c' are constants). It is also proved that the minimum number of edges in a graph which contains all planal graphs with n edges is less than cn3/2. The proofs are prohabilistic (which might not be a surprise) and short (10\% of the paper is taken up by redoubtable list of authors).
Reviewer: C.Godsil
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: universal graphs; probabilistic method
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag