9
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Matteo Jan 12 '14 at 21:05
  • 1
    $\begingroup$ @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. $\endgroup$ – Artem Kaznatcheev Jan 12 '14 at 21:28
  • $\begingroup$ 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... $\endgroup$ – Matteo Jan 12 '14 at 21:40
  • 3
    $\begingroup$ heads up the cstheory link is dead $\endgroup$ – frogeyedpeas Oct 1 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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