A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)
type: Item
instance of: scholarly article
title: A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)
zbMATH Open document ID: 0794.05111
author: Kiran B. Chilakamarri
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-08-28T00:00:00Z
review text: A unit-distance graph in \(\mathbb{R}^ n\) is a graph with a subset of \(\mathbb{R}^ n\) as the vertex set and two vertices adjacent only if their Euclidean distance is 1. It is shown that a finite graph \(G\) on \(m\) vertices is isomorhpic to a unit-distance graph in \(\mathbb{R}^ n\) if and only if there exists a real number \(\lambda\) and for arbitrarily large integers \(r\) the graph \(G\) can be drawn in the \(n\)-dimensional integer lattice \(\mathbb{Z}^ n\) such that (i) the distance between every pair of vertices is at least \(\lambda r\), and (ii) adjacent vertices have their distance in the closed interval \([r- g(r), r+ g(r)]\) with \(g(r)= 2\sqrt n/r^{1/nm}\). In the case of the Euclidean plane two variations of this result are proved.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 562390
zbMATH Keywords: unit-distance graph
zbMATH Keywords: Euclidean distance
MaRDI profile type: Publication
full work available at URL: jctb.1993.1061
OpenAlex ID: W1967572669
DOI: 10.1006/JCTB.1993.1061
description: scientific article; zbMATH DE number 562390