Note on induced subgraphs of the unit distance graph E^ n

DOI10.1007/BF02187712MaRDI QIDQ1106853zbMATH OpenFDO

Authors H. Maehara

Publication date 1989

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/131061

zbMATH Keywords

Euclidean n-spacefinite bipartite graphgraph embeddinginduced subgraphunit distance graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

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.

Recommendations

• A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)
• Embedding graphs in Euclidean space
• Embedding graphs in Euclidean space
• On the maximum number of unit edges in \(K_{m,n}\)
• Unit-distance graphs in rational n-spaces

Cites work

• Geometrical embeddings of graphs
• Helly-type theorems for spheres
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• Intersection theorems with geometric consequences
• On the dimension of a graph
• On the Euclidean dimension of a complete multipartite graph
• On the Euclidean dimension of a wheel

Cited in

(17)

• On diversity and stability of unit bases for the Euclidean metric
• A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)
• Subdividing a graph toward a unit-distance graph in the plane
• Embedding Euclidean distance graphs in \(\mathbb{R}^n\) and \(\mathbb{Q}^n\)
• Two notions of unit distance graphs
• On the maximum number of unit edges in \(K_{m,n}\)
• On the computational complexity of degenerate unit distance representations of graphs
• On the number of edges in induced subgraphs of a special distance graph
• Tearing a strip off the plane
• Algebraic Distance Graphs and Rigidity
• Cartesian product partitioning of multi-dimensional reachable state spaces
• scientific article; zbMATH DE number 5054185 (Why is no real title available?)
• The coordinate representation of a graph and \(n\)-universal graph of radius 1
• Simplices with given 2-face areas
• On the dimension to represent a graph by a unit distance graph
• Dispersed points and geometric embedding of complete bipartite graphs
• Products of unit distance graphs

This page was built for publication: Note on induced subgraphs of the unit distance graph \(E^ n\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106853)