Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 518.05044
Autor: Erdös, Paul; Sos, V.T.
Title: On a generalization of Turan's graph-theorem. (In English)
Source: Studies in pure mathematics, Mem. of P. Turan, 181-185 (1983).
Review: [This article was published in the book announced in Zbl 512.00007.]
Let t(n,k) be the number of edges in Turán's graph, i.e. the complete (k-1)-partite graph on n vertices with color classes of nearly equal sizes. The following refinement of Turán's theorem is proved: if the graph G on n vertices has more than t(n,k) edges, then there is a vertex v such that e(v) > t(d(v),k-1), where d(v) is the degree of v and e(v) is the number of edges in the graph induced by the neighbors of v. This result was proved independently by B.Bollobás and A.Thomason [Comb. Theory, Ser. B 31, 111-114 (1981; Zbl 456.05037)]; and a very short proof was published by J.A.Bondy [ibid., Ser. B 34, 109-111 (1983; Zbl 498.05041)].
Reviewer: D.de Caen
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: complete subgraphs; Turan's theorem
Citations: Zbl.512.00007; Zbl.456.05037; Zbl.498.05041
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag