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.

When we consider a graph we always want one term to get compact information about it's structure.Average distance and diameter can serve that purpose,but most of the time they turns out to be approximately equal.Can we have atleast one example where diameter is 3 times average distance in graph?

share|improve this question
    
i got some idea from Artem Kaznatcheev in link but please someone explain 'm not getting it properly... –  user997704 Jan 27 '12 at 4:38
    
please someone answer it..stuck since last hour... –  user997704 Jan 27 '12 at 4:53
1  
in general, you should try to explain what you tried already and where you are stuck. Especially for hw questions. –  Artem Kaznatcheev Jan 27 '12 at 5:05

1 Answer 1

up vote 6 down vote accepted

As I commented on cstheory just take $K_n$ and glue a path $P_{2m}$ from one of the vertices in $K_n$. The diameter is obviously $2m$, by looking at the distance between any vertex (except the one you glued to) in $K_n$ to the vertex at the end of the path $P_{2m}$.

Now, lets upper bound the average distance $\langle d \rangle$, we know that:

$$ \langle d \rangle \leq \frac{1}{n(n - 1)/2 + (2m - 1) + (2m - 1)n}\Big(n(n - 1)/2 + (2m - 1) + 2m(2m - 1)n\Big) $$

Where the normalization is by the number of edges in the graph and the first summand is sum of distances between vertexes in $K_n$ the second is for $P_m$ and the third is an upper bound on the distance between vertexes in $K_n$ and vertexes in $P_m$ (since they are each at a distance of at most $2m$ from each other).

The above equation simplifies to:

$$ \langle d \rangle \leq 1 + \frac{2(2m - 1)^2}{n - 1 + \frac{2}{n}(2m - 1) + 2(2m - 1)} $$

For $m \geq 1$ and $n \geq 2(2m - 1)(2m - 2) \in \Omega(m^2)$ this becomes:

$$ \langle d \rangle \leq 2 $$

Thus, you get the diameter $m$ times longer than the average distance.

share|improve this answer
    
I have a couple doubts on what you wrote, could you please help me understand better? 1) you say the normalization term is the number of edges in the graph. But that would simply be n(n-1)/2 for Kn and (2m-1) for P2m, so I don't understand where the third part of normalization comes from. If instead the normalization term represents the total number of paths in the graph then I don't understand at all how you got the denominator for your average distance. Thanks for any further clarification you can provide! –  Matteo Jan 12 at 21:05
    
@Matteo you are correct, I should have written that the normalized is a lower bound on the number of pairs of edges (since we are average the distance over all pairs). The argument gets even easier if we use the actual number of pairs (i.e. $\frac{1}{2}(n + 2m)(n + 2m - 1)$), I'll try to clean that up when I have a little more time. –  Artem Kaznatcheev Jan 12 at 21:28
    
Thanks a lot for confirming my idea and let me know when you get the time to clean it up! Cheers and happy new year! although a bit late... –  Matteo Jan 12 at 21:40

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.