Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 131.21001
Autor: Erdös, Pál; Rényi, Alfréd
Title: On a problem in the theory of graphs (In Hungarian)
Source: Publ. Math. Inst. Hung. Acad. Sci., Ser. B 7, 623-639 (1963).
Review: Let H2(n,k) denote the set of all (non-directed) graphs Gn having n prescribed vertices, in which the maximum of the valencies of the vertices is equal to k, and the diameter of which is \leq 2. We put F2 (n,k) = max N (Gn), Gn in H2(n,k) where N(G) denotes the number of edges of the graph G. [If H2(n,k) is empty we put F2(n,k) = +oo.] The following inequalities are proved: Theorem 1. F2(n,k) \geq n(n-1)/2k. Theorem 2. F2(n,k) \geq n(n-1)/(k+8n/k) if k2 > 8n. It is shown further by effective construction that Theorem 1 is asymptotically best possible, and that Theorem 2 is also asymptotically best possible in the case k2/n ––> +oo. The constructions are based on the use of finite geometries.
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag