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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page