# How find out whether a graph is vertex transitive?

How can I use Mathematica to find out whether a graph is vertex transitive?

• This will be included in IGraph/M 0.4 (when it is released in a couple of months), for convenience. – Szabolcs Apr 18 '17 at 10:03

I am not sufficiently familiar with the involved mathematics, so perhaps this is not the best solution. But it should work:

dog = GraphData["DodecahedralGraph"]


First we find the graph's automorphism group. (Reminder: if GraphAutomorphismGroup is too slow a for a graph, you can use IGBlissAutomorphismGroup from IGraph/M.)

group = GraphAutomorphismGroup[dog]


We need to make sure that any vertex can be mapped to any other by some automorphism. In other words, that all vertices belong to the same group orbit.

GroupOrbits[group] === {Range@VertexCount[dog]}
(* True *)


Wrapping it all up into a function, and considering special cases:

vertexTransitiveQ[g_?EmptyGraphQ] = True;
vertexTransitiveQ[g_ /; MultigraphQ[g] || MixedGraphQ[g]] = \$Failed;
vertexTransitiveQ[g_?GraphQ] :=
With[{elems = Range@VertexCount[g]},
GroupOrbits[GraphAutomorphismGroup[g], elems] === {elems}
]
vertexTransitiveQ[_] = False;


Update: This functionality is available as IGVertexTransitiveQ in the prerelease version of IGraph/M.

• Thank you. One more query. If I define – clive elphick Apr 18 '17 at 10:57
• @cliveelphick Your question is cut off. – Szabolcs Apr 18 '17 at 11:09
• not sure if last comment received. If I let G=Part[GraphData[n],1] to select first named graph in Wolfram database with n vertices, and then use GraphAutomorphismGroup[GraphData[G]] i get the message that GraphAutomorphismGroup is "not a valid group". how do I avoid this problem? Thank you. Clive – clive elphick Apr 18 '17 at 12:04
• @cliveelphick Please give a concrete GraphData command to get the problem graph (i.e. what is your n?) – Szabolcs Apr 18 '17 at 12:07
• @cliveelphick GraphAutomorphismGroup@GraphData[GraphData[3][[1]]] works fine in version 11.1.0, as well as 10.0.2. What is your version? – Szabolcs Apr 18 '17 at 12:09