Can anybody help me in finding out the distances between vertices in a vertex transitive graphs. Is there any specific formula to calculate distance between vertices in this graph. Thanks for your kind help.

In other words i want to know how to show that vertex transitive graphs are self-centered graphs. self-centered are those graphs where eccentricity is same for all vertices


closed as off topic by Aaron Meyerowitz, HJRW, Benoît Kloeckner, Andreas Blass, Chris Godsil Apr 22 '13 at 11:49

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What do you want exactly? The distance between two specific vertices? The average distance? The diameter? The number of vertices at a given distance? In case you want the distance between two specific vertices, there won't be a closed formula for that. $\endgroup$ – nvcleemp Apr 22 '13 at 8:35
  • $\begingroup$ I need to find the distance between any two arbitrary vertices of vertex transitive graph. Like we have formula to find out distances in cartesian product or strong product of graphs. Somewhere i read that they are self centered graphs i.e. eccentricity is same for all vertices or in other words radius= diamater. Is there any way to find distance between vertices of this graph? $\endgroup$ – monalisa Apr 22 '13 at 9:01

The class of vertex-transitive graphs is too wild for this question to admit a coherent answer. The set of distances between vertices can vary a great deal - some examples:

  • $K_n$, the complete graph on $n$ vertices. Here all vertices are distance 1 from each other;
  • $K_{n,n}$, the complete bipartite graph with two lots of $n$ vertices. The set of distances is $\{1,2\}$;
  • $C_n$, a cycle on $n$-vertices. The set of distances between vertices is $\{1,2,\dots, \lfloor\frac{n}{2}\rfloor\}$;

These are just a tiny set of examples from the full class - there are lots of `sporadic' examples for which the set of distances will be equally sporadic. To see this have a look at Gordon Royle's list of vertex-transitive graphs with at most 31 vertices.

Edit: I had a look through Gordon's list and noticed that the following is true: for every $n\leq 8$ and for every $a\leq \lfloor \frac{n}{2}\rfloor$, there is a vertex-transitive graph $X_{n,a}$ which has $n$ vertices and for which the set of distances is $\{1,\dots, a\}$. I wonder if this is true for all $n$?

Edit 2: The question has now been changed to ask for a proof that all vertices in a vertex-transitive graph have the same eccentricity. This is a simple consequence of vertex-transitivity, i.e. not research level.

  • $\begingroup$ @nick gill .... you are right sir... but if i am using the fact that vertex transitive graphs have vertices of same eccentricity or diameter and radius are same for such graphs, then how to do that. I am not getting any idea. It would be very kind of you if a hint is provided. thanks a lot sir $\endgroup$ – monalisa Apr 22 '13 at 9:48

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