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?


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.

| cite | improve this answer | |
  • $\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 Oct 10 '11 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 Oct 11 '11 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.