# 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
add comment

## 1 Answer

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

-
sir, i got what you said in the construction part. Can you please explain in more detail how you got the 1st part "every non-neighbor of v is at distance exaclty 2, since they have a common neighbor". thanks a lot for your concern. –  monalisa Apr 15 '13 at 17:40
Since k >= |V(G)|/2, if you take non-adjacent vertices u and v, you have |N(u)|+|N(v)|>= |V(G)|. Note that the total number of vertices is as big as the vertex set, hence, since they are not adjacent, there must be a repetition between the vertices of N(u) and N(v). –  Vinicius dos Santos Apr 17 '13 at 3:24
add comment