##
**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 G_{n} be a graph of n vertices. Denote by v(G_{n}) the capacity of G_{n} (i.e. the number of non isomorphic spanned (in other words induced) subgraphs of G_{n}). Put v(n) = **max**_{Gn} v(G_{n}). Clearly n \leq v(n) \leq 2^{n}-1. Goldberg conjectured **lim**_{n ––> oo} v(n)/2^{n} = 0. The authors disprove this conjecture and in fact prove the following stronger Theorem. For every \epsilon > 0 and almost all graphs G_{n} (i.e. all but o(2^{\binom{n}{2}} graphs G_{n}) we have v(G_{n}) > 2^{n}-2^{n(1+\epsilon)/2}. On the other hand for all graphs G_{n} we have v(G_{n}) \leq 2^{n}-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