2
$\begingroup$

Imagine I have an unknown (undirected) tree graph, $G$, with some unknown number of nodes $||V||$. However, I know the edge-length between nodes is of fixed size, $L_{edge} = 1$, and I have access to the set of distances $(d_1, ..., d_i, ..., d_M)$ between a root node, $v_{root}$, and leaf nodes, $l_i$.

When is this limited information sufficient to recover the structure of $G$, and for arbitrary $G$, beyond tree depth, what inferences might this allow?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

I think the question is a bit vague. Anyhow. You cannot recover the isomorphism type of the tree and you cannot recover the number of nodes. There is a unique tree having that set of distances with the minimal number of nodes. Namely, list the distances in increasing order $d_1,\dots,d_M$. Let $r$ be an end point of a path of length $d_1-1$. Let $v$ be the other end point. $r$ will be the root of the tree. $v$ gets one child, which becomes the leave of distance $d_1$ from the root. Also, use $v$ as the root the unique minimal tree for the distances $d_2-d_1+1,\dots,d_M-d_1+1$.

This recursive definition gives you the minimal tree with this set of distances. This tree is a quotient of every tree with this set of distances.

Improve this answer
$\endgroup$
2
  • $\begingroup$ On the other hand, if the distances between all pairs of leaves are given, the tree can be reconstructed. This is an old result that is quite famous, but I don't remember who did it. If the questioner intended that the distances be available for all possible root nodes, the answer would be different. $\endgroup$
    – Brendan McKay
    Commented Oct 10, 2011 at 23:38
  • $\begingroup$ @Brendan McKay, no I didn't intend that... but I'm certainly interested in it! If you happen to remember anything further about that old result, please do let me know. $\endgroup$
    – UltraBlue06
    Commented Oct 11, 2011 at 0:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .