Incorporamenti di grafi isomorfi nello spazio euclideo

Question

Dato un grafo non orientato e non ponderato$G = (V, E)$, è possibile trovare una mappatura$f: V \rightarrow \mathbb{R}^k$per alcuni$k$tale che per ogni$i, j \in V$,$\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, dove$\Delta(i, j)$è la lunghezza del percorso più breve tra$i$e$j$in$G$?

Ho testato alcuni controesempi per i quali questi incorporamenti isometrici in$\ell_2$non esistono (per esempio i 4 tempi), ma in questo caso funzionano.

Answer 1

Questo non è possibile in generale.

Il 4 ciclo è effettivamente utile da considerare: incorporarlo$\mathbb{R}^k$nel modo in cui descrivi richiede che le immagini di tutti e quattro i vertici siano complanari, formando un quadrato (poiché le distanze tra vertici adiacenti devono essere$1$e quelli tra le coppie non adiacenti devono esserlo$\sqrt{2}$).

Consideriamo ora il grafo bipartito completo$K_{2,3}$. Chiamiamo i suoi vertici$a_1,a_2,b_1,b_2,b_3$. In qualsiasi incorporamento$f$soddisfacendo la tua condizione, i 4 cicli$(a_1,b_1,a_2,b_2)$,$(a_1,b_1,a_2,b_3)$e$(a_1,b_2,a_2,b_3)$dovrebbero essere tutti mappati su quadrati come sopra, ma le prime due di queste condizioni implicano$f(b_2) = f(b_3)$, contraddizione.