On scale embeddings of graphs into hypercubes
type: Item
instance of: scholarly article
title: On scale embeddings of graphs into hypercubes
zbMATH Open document ID: 0773.05044
published in: European Journal of Combinatorics
publication date: 1993-05-16T00:00:00Z
review text: Suppose \(G_ 1=(V_ 1,E_ 1)\) and \(G_ 2=(V_ 2,E_ 2)\) are finite graphs. A mapping \(\varphi:G_ 1\to G_ 2\) is a scale embedding if there is an integer \(\lambda\) with \(d_ 2(\varphi(v)\), \(\varphi(v'))\leq\lambda d_ 1(v,v')\) for any pair \(v\), \(v'\) in \(V_ 1\), where \(d_ 1\) is the path metric in \(V_ 1\), and \(d_ 2\) is the path metric in \(V_ 2\). A scale embedding with \(\lambda=1\) is an isometric embedding. The paper provides three main results. (1) If \(G\) has a scale embedding into the \(n\)-cube with odd \(\lambda\), then it has an isometric embedding into the \([n/\lambda]\)-cube. For the next two results, we define the graph \(H\) to be a product of graphs \(H_ 1\), \(H_ 2,\dots,H_ r\), where each \(H_ j\) is isomorphic either to a complete graph, a cocktail party graph or a half cube. (2) If \(G\) has a scale embedding into a hypercube, there is a graph \(H\) as above and an isometric embedding \(\varphi\) of \(G\) into \(H\). (3) If \(\psi\) is a scale embedding of \(G\) into a hypercube, then there is a scale embedding \(T:G\to H\) such that \(\psi=T\varphi\), where \(\varphi\) and \(H\) are as in (2). A graph is scale embeddable in a hypercube if and only if it can be isometrically embedded in the metric space \(l_ 1\). Thus, the author is able to draw a number of corollaries concerning \(l_ 1\) embeddability from the main result.
reviewed by: M.Marx
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 168334
zbMATH Keywords: hypercubes
zbMATH Keywords: finite graphs
zbMATH Keywords: scale embedding
zbMATH Keywords: isometric embedding
author: S. Shpectorov
MaRDI profile type: Publication
full work available at URL: eujc.1993.1016
OpenAlex ID: W2066006464
DOI: 10.1006/EUJC.1993.1016
description: scientific article; zbMATH DE number 168334