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