Star graph embeddings

Question

This is an homework question which I'm struggling with:

Let $S = (V, E, w)$ a star graph, meaning, $S$ is a tree that all it's vertices are leafs except one.

I need to :

• show that every weighted star has an isometric embedding into $\ell_1$.
• find an example of a weighted star that cannot be embedded isometrically to $\ell_2$.

Couldn't really figure out how to approach this question (it's not a topic we have thoroughly covered this semester hence I'm stuck..).

Thank you very much!

Answer 1

I'm not exactly sure if this is what you want (e.g. I am confused by weights and distances mixing), but I guess the hints below might still help you (if not, let me know in the comments and I will delete this post).

Hint:

• Let $w_1, \ldots, w_n$ be the distances from the center. Check that assigning to the $i$-th node point $(0,0,\ldots,w_i,0,0,\ldots)$ satisfies your conditions (with center being just $0$).
• Set your star to have three arms of lengths 2013,2014,2015. Show that if $p_0, p_1, p_2, p_3$ is a solution where $p_0$ is the center, then $0, p_1-p_0, p_2 - p_0, p_3-p_0$ is another solution (i.e. you can assume WLOG that the center is mapped to $(0,0,0,\ldots)$). Find possible values for $p_1$ and $p_2$ (remember that the distance from $p_1$ to $p_2$ must be $w_1+w_2$). Show that there is no place to put $p_3$ so that all the distances are preserved.

I hope this helps ;-)