##
**Zentralblatt MATH**

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

**Zbl.No: ** 501.05043

**Autor: ** Erdös, Paul; Howorka, E.

**Title: ** An extremal problem in graph theory. (In English)

**Source: ** Ars Comb. 9, 249-251 (1980).

**Review: ** The distance d_{G}(u,v) between vertices u and v of a graph G is the least number of edges in any u -v path of G; d_{G}(u,v) = oo if u and v lie in distinct components of G. A graph G = (V,E) is distance-critical if for each x in V there are vertices u, v (defending on x) such that d_{G}(u,v) < d_{G-x}(u,v). Let g(n) denote the largest integer such that |E| \leq \binom{n}{2}-g(n) for every distance-critical graph on n vertices. The authors show that g(n) is of the order of magnitude n^{3/2}.

**Reviewer: ** D.Lick

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

**Keywords: ** distance; distance-critical graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag