3
$\begingroup$

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)

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

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.