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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page