Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 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)

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
Thanks! Clearly I should have thought more... –  Alain Valette Jun 19 '11 at 7:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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