MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Average squared distance in $k$-regular graphs

Let $X=(V,E)$ be a finite, connected, $k$-regular graph. Let $avg(d^2)$ be the averaged square distance between vertices, as defined in http://mathoverflow.net/questions/67838/average-squared-distance-vs-diameter-in-vertex-transitive-graphs . Is it true that $\sqrt{avg(d^2)}=\Omega(\log(|V|))$? The answer is positive for vertex-transitive graphs. ($\Omega$ is the "Big Omega" Landau notation)

-

The number of vertices in the ball of radius $c \log_k(|V|)$ ($c<1$) is small compared to $|V|$, so most pairs of vertices are more than that apart.