On the dimension to represent a graph by a unit distance graph
type: Item
instance of: scholarly article
title: On the dimension to represent a graph by a unit distance graph
zbMATH Open document ID: 0728.05053
DOI: 10.1007/BF01787703
author: H. Maehara
author: Vojtěch Rödl
published in: Graphs and Combinatorics
publication date: 1990-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 4202310
zbMATH Keywords: orthogonal representation
zbMATH Keywords: unit distance graph
Wikidata QID: Q57382218
MaRDI profile type: Publication
cites work: On the Shannon capacity of a graph
cites work: On the Euclidean dimension of a complete multipartite graph
cites work: Note on induced subgraphs of the unit distance graph \(E^ n\)
full work available at URL: https://doi.org/10.1007/bf01787703
OpenAlex ID: W2092028549
DBLP publication ID: journals/gc/MaeharaR90
Recommended article: On the metric dimension of a graph
Recommended article: Unit-Distance Graphs in Minkowski metric spaces
Recommended article: On the dimension of a graph
Recommended article: \(\varepsilon\)-unit distance graphs
Recommended article: On the connectivity of unit distance graphs
Recommended article: Finite $\epsilon$-unit distance graphs
Recommended article: Unit-distance graphs in rational n-spaces
Recommended article: Two notions of unit distance graphs
Recommended article: Q5419950
Recommended article: Q4873210
description: scientific article; zbMATH DE number 4202310