Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a tree with k nodes and for each node v the vector lv = (lv0, lv1, ..., lvk-1) with lvd the number of leaves (!) with distance d to v. I wonder whether two nodes v, w with lv = lw are conjugate (I guess they are). Can anyone help me to prove this - or give a counter example?

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
What do you think: Might the vector together with the degree be distinguishing? Or does this approach lead to nowhere? –  Hans Stricker Apr 14 '10 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 '10 at 13:05
    
I am disappointed, but you are obviously right. –  Hans Stricker Apr 14 '10 at 13:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.