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