## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  659.05075
Autor:  Caccetta, Louis; Erdös, Paul; Vijayan, K.
Title:  Graphs with unavoidable subgraphs with large degrees. (In English)
Source:  J. Graph Theory 12, No.1, 17-27 (1988).
Review:  Authors' abstract: Let G(n,m) denote the class of simple graphs on n vertices and m edges and let G in G(n,m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a Kk+1, in terms of the number of edges in G. In this paper we prove that, for m = \alpha n2, \alpha > (k-1)/2k, G contains a Kk+1, each vertex of which has degree at least f(\alpha)n and determine the best possible f(\alpha). For m = \lfloor n2/4\rfloor+1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = \alpha n2, \alpha > 0 we establish that G contains a subgraph H with \delta(H) \geq f(\alpha,n) anddetermine the best possible value of f(\alpha,n).''
Reviewer:  B.Andrasfai
Classif.:  * 05C75 Structural characterization of types of graphs
05C38 Paths and cycles
Keywords:  simple graphs; subgraphs; cycles; minimum degrees

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag