On the dimension to represent a graph by a unit distance graph (Q804603)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the dimension to represent a graph by a unit distance graph |
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
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