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