Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 Manually, I checked upto order 8 – monalisa Apr 9 '13 at 11:18
up vote 2 down vote accepted

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

share|cite|improve this answer
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
thanks for the explanation. – monalisa Apr 16 '15 at 6:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.