5
$\begingroup$

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

$\endgroup$
1
  • $\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, 2017 at 10:03

1 Answer 1

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$
8
  • $\begingroup$ Thank you. One more query. If I define $\endgroup$ Apr 18, 2017 at 10:57
  • $\begingroup$ @cliveelphick Your question is cut off. $\endgroup$
    – Szabolcs
    Apr 18, 2017 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$ Apr 18, 2017 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, 2017 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, 2017 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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