Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 245.05112
Autor: Erdös, Paul; Komlos, J.
Title: On the capacity of graphs. (In English)
Source: Period. Math. Hung. 3, 125-133 (1973).
Review: Let Gn be a graph of n vertices. Denote by v(Gn) the capacity of Gn (i.e. the number of non isomorphic spanned (in other words induced) subgraphs of Gn). Put v(n) = maxGn v(Gn). Clearly n \leq v(n) \leq 2n-1. Goldberg conjectured limn ––> oo v(n)/2n = 0. The authors disprove this conjecture and in fact prove the following stronger Theorem. For every \epsilon > 0 and almost all graphs Gn (i.e. all but o(2\binom{n{2}} graphs Gn) we have v(Gn) > 2n-2n(1+\epsilon)/2. On the other hand for all graphs Gn we have v(Gn) \leq 2n-2[n/2]-1. After submitting their paper the authors found that their main result has been proved earlier in a somewhat different form by A. D. Korshunov [Mat. Zametki 9, 263-273 (1971; Zbl 206.26201), Engl. translation in Math. Notes 9, 155-160 (1971; Zbl 226.05118)].
Classif.: * 05C35 Extremal problems (graph theory)
05C25 Graphs and groups
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag