Skip to main content
2 of 2
OP reformulated
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?

EDIT: Thanks to all for your input. The example of the complete graph is somewhat embarrassing, meaning that the OP was poorly formulated. As Aaron sort of guessed, I'm interested in families of $k$-regular graphs ($k$ fixed) with number of vertices increasing to infinity. So the new question would be: does a bound $avg(d^2)\leq \lambda(diam(X))^2$ hold for $|V|$ large enough? Observe that, for vertex-transitive graphs, the lower bound $avg(d^2)\geq\frac{(diam X)^2}{8}$ holds: see proposition 3.4 in http://toctest.cs.uchicago.edu/articles/v005a006/v005a006.pdf

Alain Valette
  • 11.1k
  • 44
  • 62