4
$\begingroup$

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?

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What do you think: Might the vector together with the degree be distinguishing? Or does this approach lead to nowhere? $\endgroup$ Apr 14, 2010 at 13:04
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 14, 2010 at 13:05
  • $\begingroup$ I am disappointed, but you are obviously right. $\endgroup$ Apr 14, 2010 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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