Note on induced subgraphs of the unit distance graph \(E^ n\)
type: Item
instance of: scholarly article
title: Note on induced subgraphs of the unit distance graph \(E^ n\)
zbMATH Open document ID: 0652.05019
DOI: 10.1007/BF02187712
author: H. Maehara
published in: Discrete \& Computational Geometry
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131061
review text: The unit distance graph \(E^ n\) is the graph whose vertices are the points in Euclidean n-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for any n there is a finite bipartite graph which cannot be embedded in \(E^ n\) as an induced subgraph and that every finite graph with maximum degree d can be embedded in \(E^ N\), \(N=(d^ 3-d)/2\), as an induced subgraph.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4063112
zbMATH Keywords: graph embedding
zbMATH Keywords: unit distance graph
zbMATH Keywords: Euclidean n-space
zbMATH Keywords: finite bipartite graph
zbMATH Keywords: induced subgraph
MaRDI profile type: Publication
cites work: Q4198785
cites work: On the Euclidean dimension of a wheel
cites work: On the dimension of a graph
cites work: Intersection theorems with geometric consequences
cites work: On the Euclidean dimension of a complete multipartite graph
cites work: Helly-type theorems for spheres
cites work: Geometrical embeddings of graphs
description: scientific article; zbMATH DE number 4063112