Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 865.05052
Autor: Erdös, Paul; Faudree, Ralph J.; Jagota, Arun; Luczak, Tomasz
Title: Large subgraphs of minimal density or degree. (In English)
Source: J. Comb. Math. Comb. Comput. 22, 87-96 (1996).
Review: Authors' abstract: This paper addresses the following questions. In any graph G with at least \alpha\binom{n}{2} edges, how large of an induced subgraph H can we guarantee the existence of with minimum degree \delta(H) \geq \lfloor\alpha|V(H)|\rfloor? In any graph G with at least \alpha\binom{n}{2}-f(n) edges, where f(n) is an increasing function of n, how large of an induced subgraph H can we guarantee the existence of containing at least \alpha\binom{|V(H)|}{2} edges? In any graph G with at least \alpha n2 edges, how large of an induced subgraph H can we guarantee the existence of with at least \alpha|V(H)|2+\Omega(n) edges? For \alpha = 1- 1/r for r = 2,3,..., the answer is zero since if G is a complete r-partite graph, no subgraph H of G has more than \alpha|V(H)|2 edges. However, we show that for all admissible \alpha except these, the answer is \Omega(n). In any graph G with minimum degree \delta(G) \geq \alpha n-f(n), where f(n) = o(n), how large of an induced subgraph H can we guarantee the existence of with minimum degree \delta(H) \geq \alpha|V(H)|?
Reviewer: B.Andrásfai (Budapest)
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: induced subgraph; minimum degree
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag