##
**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 = **{**x_{1},x_{2},...,x_{n}**}** be a set of n points in R^{d}, d \geq 2, and let R = **{**r_{1},r_{2},...,r_{n}**}** be a set of n positive real numbers. The repeated distance graph G_{d}(X,R) is the directed graph on the point set X with edges (x_{i},x_{j}) whenever d(x_{i},x_{j}) = r_{i}/d denotes Euclidean distance.

The authors present bounds on the maximum number of edges that G_{d}(X,R) can have. In addition, it is shown that \frac{n^{2}}{4} + ^{3n}/_{2} \leq f(3,d) \leq \frac{n^{2}}{4} + ^{3n}/_{2} + 255, where f(3,d) is the maximum number of edges of G_{3}(X,R) in which r_{i} = **max**_{i\ne j}d(x_{i},x_{j}) 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