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 < Ai\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 G0 = < V,E0 > such that all components of symmetric difference of G and G0 (denoted by G\DeltaG0 = < V,E\DeltaE0 >) have sizes at most m.
The authors and (independently) N. Alon and B. Bollobás prove the following result. Let i(G) = o(n2). 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 nk+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 Kc log n,c log n\not\subset G,\bar G, where Kn,m is bipartite graph, \bar G is the complement of G. Then for every sufficiently large n, i(G) \geq 2n/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