Given a tree $T$ and a vertex $v$ in $T$, let $N_r(T)$ be the set of all vertices at distance at most $r$ to $v$. Furthermore, let $T_r(v) = T[N_r(v)]$, the subtree of $T$ induced by $N_r(v)$. Fix $v$ and let its neighbors be $w_1,\ldots, w_t$. Suppose that we know $T_r(v)$ as well as the multiset $\{\{ T_r(w_1),\ldots, T_r(w_t)\}\}$. Can we reconstruct $T_{r+1}(v)$ from these? I want to prove that indeed this is the case.

My attempt goes as follows using induction. Clearly the $r=0$ case is simple as we have $T_0(v)=T_0(w_1)=\ldots = T_0(w_t)$, all singleton graphs. Then $T_{1}(v)$ is simply the star with $t$ legs, where $t$ is the size of the multiset. Now, suppose that the statement is true for $r$. Then, if we have $T_r(v)$ and $T_r(w_1),\ldots, T_{r}(w_t)$, then we need to somehow puzzle these trees together. This is possible, because we started with a tree $T$, we can compute $T_{r+1}(v)$, and it can be obtained by puzzling together the rooted trees in some way. But would the result be unique?

Perhaps the result is not true and we should instead look at rooted trees. In this case the base case of the induction step is the same, we obtain the rooted star. For the induction step we then have a set of rooted trees. We know that each of the roots of the $T_r(w_j)$ needs to be a neighbor of the root of $T_r(v)$. Can it be uniquely done in this case?

It seems to me that in this case we can look at the isomorphism classes of the branches of $T_r(v) - v$, if these are all distinct then the problem should be easier but still I am not sure...

Thanks in advance for any help!

P.S. This question is somewhat reminiscent of the reconstruction conjecture, which is solved for trees. Perhaps we can determine the deck for $T_{r+1}(v)$.

  • $\begingroup$ What counts as reconstruction? There can be edges in $T_{r+1}(v)$ that do not occur in any of the $T_r(w_i)$, since vertices a full distance of $r+1$ from $v$ may be neighbors, but lie in different $T_r(w_i)$. Does your construction allow you to pull in these new edges? $\endgroup$ – Paul Sinclair Oct 10 at 0:17
  • $\begingroup$ If I am not mistaken what you are saying is incorrect because $T$ is a tree. If such neighbors exists and lie in $T_r(w_i)$ and $T_r(w_j)$ then there is a cycle through $w_i,v,w_j$ right? By a reconstruction I mean that we can exactly identify the isomorphism class of $T_{r+1}(v)$, i.e., we may draw it out exactly $\endgroup$ – Slugger Oct 10 at 7:32
  • $\begingroup$ Your are right - I was thinking "rooted graph", not tree. For trees this works. $\endgroup$ – Paul Sinclair Oct 10 at 16:41
  • $\begingroup$ Thats great :P Anything in the way of a hint or link? $\endgroup$ – Slugger Oct 10 at 17:09

Your Answer

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

Browse other questions tagged or ask your own question.