## 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) = c3/2k2/2+o(k2). Several proofs are provided.
Reviewer:  W.G.Brown
Classif.:  * 05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag