On the euclidean dimension of a complete multipartite graph

AbstractThe euclidean dimension of a graph G, e(G), is the minimum n such that the vertices of G can be placed in euclidean n-space, Rn, in such a way that adjacent vertices have distance 1 and nonadjacent vertices have distances other than 1. Let G=K(n1,...,ns+t+u) be a complete (s+t+u)-partite graph with vertex-classes consisting of s sets of size 1, t sets of size 2, and u sets of size ⩾3. We prove that e(G)=s+t+2u if t+u⩾2, and e(G)=s+t+2u-1 if t+u⩽1