Skip to main content
1 of 2
Alain Valette
  • 11.1k
  • 44
  • 62

Average squared distance vs diameter in vertex-transitive graphs

Let $X=(V,E)$ be a finite, connected graph on $n$ vertices, endowed with its graph metric $d$. The average squared distance of $X$ is $avg(d^2)=\frac{1}{n(n-1)}\sum_{x,y\in V,x\neq y} d(x,y)^2$; it satisfies the obvious bound $avg(d^2)\leq diam(X)^2$, where $diam(X)$ is the diameter of $X$.

Now assume that $X$ is vertex-transitive. My intuition is that, in this case, for ``many'' pairs of vertices, the distance is much smaller than the diameter, which should entail an inequality $avg(d^2)\leq \lambda(diam(X))^2$, where $\lambda<1$ is some constant, maybe depending only on the common degree of the vertices. Is this intuition correct? If yes, can $\lambda$ be estimated?

Alain Valette
  • 11.1k
  • 44
  • 62