Note on induced subgraphs of the unit distance graph \(E^ n\) (Q1106853)

From MaRDI portal
Revision as of 17:26, 18 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Note on induced subgraphs of the unit distance graph \(E^ n\)
scientific article

    Statements

    Note on induced subgraphs of the unit distance graph \(E^ n\) (English)
    0 references
    0 references
    1989
    0 references
    The unit distance graph \(E^ n\) is the graph whose vertices are the points in Euclidean n-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for any n there is a finite bipartite graph which cannot be embedded in \(E^ n\) as an induced subgraph and that every finite graph with maximum degree d can be embedded in \(E^ N\), \(N=(d^ 3-d)/2\), as an induced subgraph.
    0 references
    graph embedding
    0 references
    unit distance graph
    0 references
    Euclidean n-space
    0 references
    finite bipartite graph
    0 references
    induced subgraph
    0 references

    Identifiers