##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 668.05037

**Autor: ** Erdös, Paul; Hajnal, András

**Title: ** On the number of distinct induced subgraphs of a graph. (In English)

**Source: ** Discrete Math. 75, No.1-3, 145-154 (1989).

**Review: ** Let i(G) be the number of pairwise non-isomorphic induced subgraphs of graph G = < V,E > . The graph G = < V,E > is \ell-canonical if there is a partition < A_{i}\subset V: 0 \leq i < \ell > such that **{**x,y**}** in E <==> **{**x',y'**}** in E for all i,j < 1, x,x' in A, y,y' in A. The graph G = < V,E > is (\ell,m)-almost canonical if there is an \ell-canonical graph G_{0} = < V,E_{0} > such that all components of symmetric difference of G and G_{0} (denoted by G_{\Delta}G_{0} = < V,E_{\Delta}E_{0} >) have sizes at most m.

The authors and (independently) N. Alon and B. Bollobás prove the following result. Let i(G) = o(n^{2}). Then one can omit o(n) vertices of G in such a way that the remaining graph is either complete or empty. In the paper the following stronger theorem is proved.

Theorem 1. For all \epsilon > 0 and for all k \geq 1 there exists a \delta > 0 such that for all n and for all G with n vertices i(G) \leq \delta n^{k+1} it follows that these exists a W\subset V, |W| \leq \epsilon n, such that G[V**\** W] is (\ell,m)-almost canonical for some \ell, m satisfying \ell+m, k+1. In addition the following estimation is obtained.

Theorem 2. Let G be a graph with n vertices, c > 0, k > 2c log 2 and K_{c log n,c log n}\not\subset G,\bar G, where K_{n,m} is bipartite graph, \bar G is the complement of G. Then for every sufficiently large n, i(G) \geq 2^{n/4k}.

**Reviewer: ** Yu.M.Voloshin

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C30 Enumeration of graphs and maps

**Keywords: ** induced subgraphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag