Regular embeddings of a graph

Abstract

In this paper we study embeddings of a graph G in Euclidean space R" that are 'regular' in the following sense: given any two distinct vertices u and v of G, the distance between the corresponding points in R" equals a if u and v are adjacent, and equals otherwise. It is shown that for any given value of s -( 2 -a 2 )/ 2 9 the minimum dimension of a Euclidean space in which G is regularly embeddable is determined by the characteristic polynomials of G and (7.