Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If the tree is a path of length $n$, and you apply the operation to that path, you get a star, in which the longest path is of length $3>n-n+(1-1)=0$. –  Brian M. Scott Apr 8 '12 at 18:48
    
Aha, how did I missed that. I measure the length of a path by the number of edges. In that case we have 2>1. so I think one small change make it work. Simply have +k instead of +(k-1). –  Chao Xu Apr 9 '12 at 3:14
    
If you’re measuring the path length by edges, you want to change the path in the second paragraph to $v_0v_1v_2\dots v_m$, so that it has $m$ edges instead of $m$ vertices. –  Brian M. Scott Apr 9 '12 at 3:15
    
aha I see, thanks. fixed. –  Chao Xu Apr 9 '12 at 3:24

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
    
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'. –  Chao Xu Apr 12 '12 at 14:53

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.