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$
3
  • $\begingroup$ i got some idea from Artem Kaznatcheev in link but please someone explain 'm not getting it properly... $\endgroup$
    – user997704
    Jan 27, 2012 at 4:38
  • $\begingroup$ please someone answer it..stuck since last hour... $\endgroup$
    – user997704
    Jan 27, 2012 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$ Jan 27, 2012 at 5:05

1 Answer 1

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$
5
  • 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, 2014 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$ Jan 12, 2014 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, 2014 at 21:40
  • 3
    $\begingroup$ heads up the cstheory link is dead $\endgroup$ Oct 1, 2019 at 2:25
  • $\begingroup$ Can you please sketch the graph? what is K_n, or how the diameter is only 2m, if K_n means K connected graph? $\endgroup$
    – DsCpp
    Dec 2, 2019 at 9:29

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.