Recovering tree structure from pairwise distances

150 Views Asked by At

Given some tree, one can create a set of lengths of shortest paths and their multiplicities.

For example, the tree $P_4$ has one shortest path of length 3, two shortest paths of length 2, and three shortest paths of length 1. The corresponding set would then be $D_{P_4} = \{(1,3), (2,2), (3,1)\}$. Thus, if $(a, b) \in D_T$, then there are exactly $a$ pairs of vertices $\{u, v\}$ such that $\mathrm{dist}(u,v) = b$ in tree $T$.

We need to account for ${n \choose 2}$ paths for a tree with $n$ vertices.

My question has to do with reconstructing the tree. That is, given such a set as above (and given that the set was indeed derived from a tree), can we uniquely reconstruct the tree it comes from?

1

There are 1 best solutions below

0
On BEST ANSWER

Randić had conjecture, that even more strong property of equality of distance degree sequences implies isomorphism of trees. But there are counterexamples to Randić's conjecture, one of them is below.

enter image description here

Both trees have the same distance degree sequence that is essentially the same as multiset $$\{\,\{\,d(v, u) \quad \forall u\in V(G)\,\} \quad \forall v \in V(G)\,\}$$ of multisets of distances $d(v, u)$ from each vertex $v$ to all other vertices.

P. S. It is easy to check that in your notation we have $D_{T_1} = D_{T_2} = \{\,(16, 5), (42, 4), (48, 3), (30, 2), (17, 1)\,\}$ for trees $T_1$ and $T_2$ above.