On the Euclidean dimension of a complete multipartite graph (Q1110525): Difference between revisions

The Euclidean dimension, e(G), of a graph G is defined to be the minimum n such that the vertices of G can be placed in Euclidean n-space, \(R^ n\), so that two vertices are adjacent if and only if the Euclidean distance between them is 1. This parameter has been determined for complete bipartite graphs by Lenz [see \textit{P. Erdős, F. Harary} and \textit{W. T. Tutte}, Mathematika 12, 118-122 (1965; Zbl 0151.332), and for complete tripartite graphs by \textit{Buckley} and \textit{F. Harary}, Graphs and Combinatorics 4, 22-30 (1988)]. Now let \(G=K(n_ 1,...,n_{s+t+u})\) be a complete \((s+t+u)\)-partite graph with s partite sets of order 1, t of order 2, and u of order \(\geq 3\). The present paper generalizes the two previously mentioned to show that \[ e(G)=s+t+2u,\quad if\quad t+u\geq 2;\quad e(G)=s+t+2u-1,\quad if\quad t+u\leq 1. \]