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