Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 358.05027
Autor: Erdös, Paul; Kleitman, Daniel J.; Rothschild, B.L.
Title: Asymptotic enumeration of Kn-free graphs. (In English)
Source: Colloq. int. Teorie comb., Roma 1973, Tomo II, 19-27 (1976).
Review: [For the entire collection see Zbl 348.00004.]
This paper is devoted to the proofs of the following two results.
Result 1: Let Gk(n) be the number of graphs with n vertices and with no complete subgraphs on k vertices. Then log2(Gk(n)) = \frac{n2}2(1-\frac1{k-1})+O(n2).
Result 2: Let Tn be the number of graphs with n vertices and with no complete subgraphs on 3 vertices; let Sn be the number of bipartite graphs on n-vertices. Then Tn = Sn(1+o( 1/n )).
Reviewer: J.E.Graver
Classif.: * 05C30 Enumeration of graphs and maps
05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag