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 Average squared distance vs diameter in vertextransitive graphs . Is it true that $\sqrt{avg(d^2)}=\Omega(\log(V))$? The answer is positive for vertextransitive graphs. ($\Omega$ is the "Big Omega" Landau notation)
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
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. 

