On the dimension to represent a graph by a unit distance graph (Q804603)

From MaRDI portal





scientific article
Language Label Description Also known as
English
On the dimension to represent a graph by a unit distance graph
scientific article

    Statements

    On the dimension to represent a graph by a unit distance graph (English)
    0 references
    0 references
    0 references
    1990
    0 references
    A unit distance graph in Euclidean n-space \(R^ n\) is a graph with vertex set V in \(R^ n\) and edge set \(\{\{x,y\}:\;| x-y| =1,\quad x,y\in V\}.\) For a graph G, let \(\dim_ 1G\) denote the minimum dimension n such that G is isomorphic to a unit distance graph in \(R^ n.\) The authors prove that if a graph G has maximum degree d, then its vertices can be represented by distinct unit vectors in \(R^{2d}\) so that two vectors are orthogonal if and only if the corresponding unit vectors are adjacent. This result implies that if a graph has maximum degree d, then \(\dim_ 1G\leq 2d.\) A graph is said to be d-degenerate if every subgraph of G has a vertex of degree\(\leq d\). Using the above mentioned result it can also be shown that if a graph G is d-degenerate, then \(\dim_ 1G\leq 2d+1\).
    0 references
    orthogonal representation
    0 references
    unit distance graph
    0 references

    Identifiers