##
**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 K_{k+1}, in terms of the number of edges in G. In this paper we prove that, for m = \alpha n^{2}, \alpha > (k-1)/2k, G contains a K_{k+1}, each vertex of which has degree at least f(\alpha)n and determine the best possible f(\alpha). For m = \lfloor n^{2}/4\rfloor+1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = \alpha n^{2}, \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