Skip to main content

Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, where $\Delta(i, j)$ is the shortest path lenghtlength between $i$ and $j$ in $G$?

I have been testing a few counterexamples for which these isometric embeddings in $\ell_2$ fail to exist (for example, the 4-ciclecycle), but in this case they workswork.

Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, where $\Delta(i, j)$ is the shortest path lenght between $i$ and $j$ in $G$?

I have been testing few counterexamples for which these isometric embeddings in $\ell_2$ fail to exist (for example, the 4-cicle), but in this case they works.

Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, where $\Delta(i, j)$ is the shortest path length between $i$ and $j$ in $G$?

I have been testing a few counterexamples for which these isometric embeddings in $\ell_2$ fail to exist (for example, the 4-cycle), but in this case they work.

Tweeted twitter.com/StackCSTheory/status/1296280953229398016
Became Hot Network Question
Source Link
Andrea
  • 319
  • 1
  • 6

Isomorphic graph embeddings in the Euclidean Space

Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, where $\Delta(i, j)$ is the shortest path lenght between $i$ and $j$ in $G$?

I have been testing few counterexamples for which these isometric embeddings in $\ell_2$ fail to exist (for example, the 4-cicle), but in this case they works.