3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you be a bit more specific about what you mean by a walk of length $k$? some obvious interpretations admit obvious counterexamples, so some clarity would help. $\endgroup$
    – Vladimir Dotsenko
    Commented Jan 12, 2016 at 12:35
  • $\begingroup$ Just a sequence of edges $(v_1,v_2),(v_2,v_3),\dots,(v_{k-2},v_{k-1})$. And I'm also requiring that $v_1$ be the root. The paths are allowed to end wherever, and any amount of backtracking is allowed; these walks do not have to be simple. They can repeat edges and vertices. It's quite possible I missed some easy counterexample. $\endgroup$
    – batconjurer
    Commented Jan 12, 2016 at 12:53
  • $\begingroup$ As for me, possible counterexanples probably can be found among pairs of isospectral trees. Do you have any software to check whether your condition is satisfied? If so, I would suggest to test some pairs from, e.g., pubs.acs.org/doi/pdf/10.1021/ci970242r (parhaps, those on Fig. 5?). $\endgroup$
    – Ilya Bogdanov
    Commented Jan 12, 2016 at 13:13
  • $\begingroup$ Sure, I can give that a shot. $\endgroup$
    – batconjurer
    Commented Jan 12, 2016 at 13:35

1 Answer 1

Reset to default
8
$\begingroup$

Take a 9-cycle with vertices $\{0,\ldots,8\}$ and join new vertices of degree one to 0, 3, 6. Delete the vertex 8 from the cycle, producing a tree $T$ on 11 vertices. Then $T\backslash 2\cong T\backslash 5$, but no automorphism of $T$ maps 2 to 5.

Now there is a theorem that if $u$ and $v$ are vertices in graph $X$ and $X\backslash u$ and $X\backslash v$ are cospectral and their complements are cospectral, the generating functions for closed walks at $u$ and for all walks at $u$ are equal to the corresponding generating functions for walks at $v$. (This is a consequence of results from chapter 4 in my book "Algebraic Combinatorics".)

So vertices 2 and 5 cannot be distinguished by your criterion. (My example is quite likely not minimal.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm a bit confused by your answer. First of all, $T$ was formed by deleting vertex 8, so I don't know what it means for $T$ to have no automorphism taking 5 to 8. If $T$ is the graph with 8 still in, then indeed $T\setminus 5\cong T\setminus 8$, but no roots are specified for me to check the condition. Clarification would be greatly appreciated. (Also, I should apologize as I added a clarification as a comment earlier that I should have put in the question. Walks are not assumed to be simple. I don't know if that changes your example) $\endgroup$
    – batconjurer
    Commented Jan 12, 2016 at 14:39
  • $\begingroup$ @Ilya Bogdanov: thanks, I've made the appropriate edits. $\endgroup$
    – Chris Godsil
    Commented Jan 12, 2016 at 15:04
  • $\begingroup$ @Ilya Bogdanov : Chris and I found this example in our first paper together (1975), see Fig 7 at users.cecs.anu.edu.au/~bdm/papers/GodsilMcKayComputational.pdf . I'm sure it is the first example where the two rooted trees are isomorphic if the root is ignored, but plausibly there are smaller examples without that property. $\endgroup$
    – Brendan McKay
    Commented Jan 12, 2016 at 19:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .