Welcome to MathOverflow

Question

3

Consider a tree with k nodes and for each node v the vector l^v = (l^v₀, l^v₁, ..., l^v_k-1) with l^v_d the number of leaves (!) with distance d to v. I wonder whether two nodes v, w with l^v = l^w are conjugate (I guess they are). Can anyone help me to prove this - or give a counter example?

flag	asked Apr 14 2010 at 11:58 Hans Stricker 5,233●12●38

Joel David Hamkins · Accepted Answer · 2010-04-14 12:56:16Z UTC

6

I have a counterexample. It is not enough just to count leaves, since this doesn't take into account the number of possible ways to arrive at those leaves.

Consider the graph below.

   A - B - C - D - E - F
           |       |
           G       H
           |
           I

I think the vector for C and D both is 002200000, since they each have two leaves at distance 2 and two leaves at distance 3. But they are not conjugate, since C has degree 3 and D has degree 2.

I think this might be a minimal counterexample.

answered Apr 14 2010 at 12:56

Joel David Hamkins
74.9k●7●187●343

What do you think: Might the vector together with the degree be distinguishing? Or does this approach lead to nowhere? – Hans Stricker Apr 14 2010 at 13:04

1

I don't think so, because you can insert C' and D' between C and D above, and get a counterexample with C' and D', but they would both have degree 2. What you need is the degree of all the nodes connecting them to the leaves, which is to say, what you need is the whole graph. – Joel David Hamkins Apr 14 2010 at 13:05

I am disappointed, but you are obviously right. – Hans Stricker Apr 14 2010 at 13:10

A distinguishing node property in trees?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.