On the dimension to represent a graph by a unit distance graph
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\).
scientific article; zbMATH DE number 4202310