# Eccentricity of vertices in a graph

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?

-
There are some trivial restrictions like the degree equals to |V(G)|-1 or |V(G)|-2. Is that the kind of restriction you are looking for? –  Vinicius dos Santos Apr 9 '13 at 10:33
@ViniciusF.dosSantos yes sir, like that or like restriction on number of vertices. but the graph should be regular. Thanks for your concern. –  monalisa Apr 9 '13 at 11:00
@ViniciusF.dosSantos i tried for graphs given in the link mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG. Manually, I checked upto order 8 –  monalisa Apr 9 '13 at 11:18

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$.