On the Euclidean dimension of a complete multipartite graph (Q1110525)

From MaRDI portal
Revision as of 10:22, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
On the Euclidean dimension of a complete multipartite graph
scientific article

    Statements

    On the Euclidean dimension of a complete multipartite graph (English)
    0 references
    0 references
    1988
    0 references
    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. \]
    0 references
    Euclidean dimension
    0 references
    Euclidean n-space
    0 references
    complete bipartite graphs
    0 references
    complete tripartite graphs
    0 references

    Identifiers