Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 405.05031
Autor: Erdös, Paul; Hajnal, András
Title: On spanned subgraphs of graphs. (In English)
Source: Beiträge zur Graphentheorie und deren Anwendungen, vorgetr. auf dem int. Kolloq., Oberhof (DDR) 1977, 80-96 (1977).
Review: [For the entire collection see Zbl 387.00005.]
In this paper, theorems of the following type are proved: Let C be a class of (finite) graphs satisfying certain asymptotic conditions saying that for G in C, both G and its complement \overline G are large. Then for all G in C and all H in some specified class of graphs, H is isomorphic to an induced subgraph of G provided the order of G is large enough compared to the order of H, where the order of a graph is the number of vertices. Examples of two such results are the following. Theorem 1. Let \delta > 0 and C(\delta) be the class of graphs G satisfying \degGx \geq (\delta+1/4)n and \deg\overline G \geq (\delta+1/4)n for all x in V(G), where n is the order of G. Then there are functions n(\delta), c(\delta) such that for all G in C(\delta) with |V(G)| > n(\delta) and for all H in D with | V(H)| \leq c(\delta) log n, where D is the class of complete bipartite graphs and their complements, H is isomorphic to an induced subgraph of G. Theorem 2. Let c be a real number, and let C be the class of graphs G such that neither G nor its complement contains a complete graph with at least c log n vertices, where n is the order of G. Then there is a function n(c,k) such that for all graphs G in C with at least n(c,k) vertices and for all graphs H of order k, H is isomorphic to an induced subgraph of G.
Reviewer: L.Lesniak-Foster
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: spanned subgroups of graphs
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag