1
$\begingroup$

I was looking at this operation in a tree, and try to relate it to the diameter of the tree.

Pick a path of length $m$, so let it be $v_1v_2\ldots v_mv_{m+1}$. Remove all the edges in the path, and add edge $v_1v_j$, where $2 \leq j\leq m+1$. It is easy to see the resulting graph is still a tree.

Intuitively, it replace a long path with many smaller paths.

I conjecture the longest path in a tree of $n$ vertices after doing this operation $k$ times, $i$th time act on a path of length $l_i$, is at most $n-\sum_{i=1}^k l_i + k$.

I have a hard time proving it or show a counterexample, because it is not easy to come up with a characterization of the tree after each operation. It is possile the longest path does not change at all in a sequece of operations.

I hope to find pointers to anything known about this kind of operations.

  • 0
    aha I see, thanks. fixed.2012-04-09

1 Answers 1

1

I believe that I’ve found a counterexample to the conjecture. Consider the tree shown below:

                        1                           |                        2--3--4--5                           |                           6 

Perform your operation on the path $2345$, taking $5$ as the ‘centre’:

                        1  2                           |  |                           3--5                           |  |                           6  4 

Now perform it again on the path $1352$, taking $2$ as the ‘centre’:

                              1                                 |                           6--3--2--5--4   

We have $n=6$, $l_1=l_2=3$, and $k=2$, so $n-(l_1+l_2)+k=2$, but the third graph has a path of length $4$.

  • 0
    A good counterexample! Indeed doing this one can create longer path than before. However I wonder what happens if we give a ordering to the vertices, and one must pick the smallest vertex as the 'center'.2012-04-12