Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 656.05039
Autor: Avis, David; Erdös, Paul; Pach, János
Title: Repeated distances in space. (In English)
Source: Graphs Comb. 4, No.3, 207-217 (1988).
Review: Let X = {x1,x2,...,xn} be a set of n points in Rd, d \geq 2, and let R = {r1,r2,...,rn} be a set of n positive real numbers. The repeated distance graph Gd(X,R) is the directed graph on the point set X with edges (xi,xj) whenever d(xi,xj) = ri/d denotes Euclidean distance.
The authors present bounds on the maximum number of edges that Gd(X,R) can have. In addition, it is shown that \frac{n2}{4} + 3n/2 \leq f(3,d) \leq \frac{n2}{4} + 3n/2 + 255, where f(3,d) is the maximum number of edges of G3(X,R) in which ri = maxi\ne jd(xi,xj) holds.
Reviewer: P.Horák
Classif.: * 05C35 Extremal problems (graph theory)
05C20 Directed graphs (digraphs)
05C38 Paths and cycles
Keywords: furthest neighbor graph; repeated distance graph
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag