5
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Thank you. One more query. If I define $\endgroup$ – clive elphick Apr 18 '17 at 10:57
  • $\begingroup$ @cliveelphick Your question is cut off. $\endgroup$ – Szabolcs Apr 18 '17 at 11:09
  • $\begingroup$ 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 $\endgroup$ – clive elphick Apr 18 '17 at 12:04
  • $\begingroup$ @cliveelphick Please give a concrete GraphData command to get the problem graph (i.e. what is your n?) $\endgroup$ – Szabolcs Apr 18 '17 at 12:07
  • $\begingroup$ @cliveelphick GraphAutomorphismGroup@GraphData[GraphData[3][[1]]] works fine in version 11.1.0, as well as 10.0.2. What is your version? $\endgroup$ – Szabolcs Apr 18 '17 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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