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?

  • 1
    $i$n general, you should try to explain what you tried already and where you are stuck. Especially for hw questions.2012-01-27

1 Answers 1

8

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.

  • 0
    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...2014-01-12