##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 674.05040

**Autor: ** Caccetta, Louis; Erdös, Paul; Vijayan, K.

**Title: ** On graphs with adjacent vertices of large degree. (In English)

**Source: ** J. Comb. Math. Comb. Comput. 5, 217-222 (1989).

**Review: ** Let {\frak G}(n,m) be the class of finite, loopless graphs G without multiple edges on n vertices and m edges. An important problem in extremal graph theory is the determining the maximum m such that {\frak G}(n,m) contains at least one graph G which has no subgraph isomorphic to any given graph on n or fewer vertices.

Continuing these previous investigations the authors of this paper get to the following results with respect to the degree of adjacent vertices:

Let be m = \alpha n^{2}, then holds

- G in {\frak G}(n,m) contains a pair of adjacent vertices each having degree (in G) at least f(\alpha). n and the best possible value of f(\alpha) is determined (Theorem 1);

- In the case \alpha > ^{1}/_{4} ^{G} obtains a triangle with a pair of vertices satisfying the degree restriction of theorem 1 (Theorem 2).

Finally are discussed two further open problems.

**Reviewer: ** H.-J.Presia

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C75 Structural characterization of types of graphs

**Keywords: ** adjacent vertices of large degree in the class of simple graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag