Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  Brendan McKay Oct 10 '11 at 23:38
    
@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. –  UltraBlue06 Oct 11 '11 at 0:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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