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 n2, 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