Eccentricity of vertices in a graph

Question

This question is related to my last question about regular graphs Eccentricity of vertices in a regular graph. I got the required answer but I am having a doubt.
Can we put restriction on number of vertices and regularity so that the graph contains vertices of same eccentricity?

Answer 1

The more general condition of this type I can think about is the following:

If $G$ is a $k$-regular graph and $k \geq \frac{|V(G)|}{2}$, then all vertices have the same eccentricity. To see this, note that either $G$ is a complete graph or for every vertex $v$, every non-neighbor of $v$ is at distance exaclty $2$, since they have a common neighbor.

Actually I think this is almost optimal, since one can build one example similar to the one presented by Chris Godsil in the other question: just take a complete graph on $2r$ vertices, remove a matching of size $r-1$ and add a new vertex $v$, adjacent to every vertex with degree $2r-2$. Note that now every vertex has degree $2r-1$, except for $v$, which has degree $2r-2$. Now make a copy of the graph and let $v'$ be the copy of $v$. Finally, add an edge between $v$ and $v'$. Note that the final graph is $(2r-1)$-regular and the eccentricity is not the same for every vertex. Let $k = 2r-1$. Note that $G$ is $k$-regular, with $|V(G)|=4r+2$ and hence $k = \frac{|V(G)|}{2}-2$.