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\).
- On the metric dimension of a graph
- Unit-Distance Graphs in Minkowski metric spaces
- On the dimension of a graph
- -unit distance graphs
- On the connectivity of unit distance graphs
- Finite -unit distance graphs
- Unit-distance graphs in rational n-spaces
- Two notions of unit distance graphs
- Two notions of unit distance graphs
- scientific article; zbMATH DE number 866045
- Dot product representations of graphs
- On representations of graphs as two-distance sets
- Two notions of unit distance graphs
- Infinite quantum permutations
- On the computational complexity of degenerate unit distance representations of graphs
- Unit distance representations of the Petersen graph in the plane.
- The coordinate representation of a graph and \(n\)-universal graph of radius 1
- Kernelization for H-coloring
- Products of unit distance graphs
This page was built for publication: On the dimension to represent a graph by a unit distance graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804603)
