Skip to main content
added 208 characters in body
Source Link
batconjurer
  • 928
  • 4
  • 11

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to the number of walks of $T_2$ starting at $r_2$ of length $k$. Is it true that $T_1$ and $T_2$ are isomorphic as rooted trees?

It seems to me strange that this would be true and I cannot find any mention of it. On the other hand, I can't seem to come up with a counterexample.

EDIT: Apologies! I should have said that walks are not assumed to be simple or closed! A walk is just a sequence of adjacent edges, edges and vertices may be repeated and the ending point does not matter.

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to the number of walks of $T_2$ starting at $r_2$ of length $k$. Is it true that $T_1$ and $T_2$ are isomorphic as rooted trees?

It seems to me strange that this would be true and I cannot find any mention of it. On the other hand, I can't seem to come up with a counterexample.

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to the number of walks of $T_2$ starting at $r_2$ of length $k$. Is it true that $T_1$ and $T_2$ are isomorphic as rooted trees?

It seems to me strange that this would be true and I cannot find any mention of it. On the other hand, I can't seem to come up with a counterexample.

EDIT: Apologies! I should have said that walks are not assumed to be simple or closed! A walk is just a sequence of adjacent edges, edges and vertices may be repeated and the ending point does not matter.

Source Link
batconjurer
  • 928
  • 4
  • 11

A criterion for rooted trees to be isomorphic based on walks

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to the number of walks of $T_2$ starting at $r_2$ of length $k$. Is it true that $T_1$ and $T_2$ are isomorphic as rooted trees?

It seems to me strange that this would be true and I cannot find any mention of it. On the other hand, I can't seem to come up with a counterexample.