##
**Zentralblatt MATH**

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

**Zbl.No: ** 353.05045

**Autor: ** Bollobás, Béla; Erdös, Paul

**Title: ** An extremal problem of graphs with diameter 2. (In English)

**Source: ** Math. Mag. 48, 281-283 (1975).

**Review: ** For integers p and k such that 1 \leq k < p, m(p,k) is the minimum number of edges for which there exists a graph on p vertices, every pair of which are connected by at least k paths of length 1 or 2. *U.S.R.Murty* [On critical graphs of diameter 2, Math. Mag. 41, 138-140 (1968; Zbl 167.22102)] proved that if p \geq (½)(3+\sqrt 5)k, then m(p,k) = \binom p2-\binom {p-k}2 and characterized the unique extremal graph. The Theorem of this paper states that if 1 < c < (½)(3+\sqrt 5), then m([ck],k) = c^{3/2}k^{2}/2+o(k^{2}). Several proofs are provided.

**Reviewer: ** W.G.Brown

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

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag