## 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 dG(u,v) between vertices u and v of a graph G is the least number of edges in any u -v path of G; dG(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 dG(u,v) < dG-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 n3/2.
Reviewer:  D.Lick
Classif.:  * 05C35 Extremal problems (graph theory)
Keywords:  distance; distance-critical graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag