# Generate graphs from the output of GraphAutomorphismGroup

Given

g = Graph[{1 -> 2, 2 -> 3, 3 -> 1, 4 -> 1, 1 -> 5, 5 -> 4}, VertexLabels -> "Name"]
GraphAutomorphismGroup[g]


outputs

PermutationGroup[{Cycles[{{2, 5}, {3, 4}}]}]

which I understand as changing 2 -> 5, and 3 -> 4 will give an automorphic graph. This is true when tested:

g2 = Graph[{1 -> 5, 5 -> 4, 4 -> 1, 3 -> 1, 1 -> 2, 2 -> 3}, VertexLabels -> "Name"]
IsomorphicGraphQ[g, g2]


True

With any given graph, I want to explicitly generate all the automorphic graphs (cause I want to compare adjacency matrices), can I use PermutationGroup and Cycles to do this or it's easier if I just dump these parts of the expression and use Replace?

ClearAll[f]
f = With[{g = #,  vl = VertexList[#],
pvl = Permute[ VertexList[#], GraphAutomorphismGroup[#]]},
{VertexLabels -> "Name", ImageSize -> 300}]& /@ pvl]&;

g = Graph[{1 -> 2, 2 -> 3, 3 -> 1, 4 -> 1, 1 -> 5, 5 -> 4}, VertexLabels -> "Name"]


Row[f @ g]


Row[f @ CycleGraph[5, VertexLabels->"Name", DirectedEdges->True]]


And @@ (IsomorphicGraphQ[g2, #] & /@ f[g2])


True

g3= PetersenGraph[5,2];
And@@(IsomorphicGraphQ[g3,#]&/@f[g3])


True

• You just get five automorphic graphs, but it has ten.
– yode
Commented Jul 2, 2022 at 14:14
AutomorphicGraphs[g_] := VertexReplace[g, Thread[VertexList[g] -> #]] & /@
Permute[VertexList[g], GraphAutomorphismGroup[g]]


g1=Graph[{1->2,2->3,3->1,4->1,1->5,5->4},VertexLabels->"Name"];
AutomorphicGraphs[g1]


IsomorphicGraphQ[g1,#]&/@%


{True,True}

For the cycle graph:

g2=CycleGraph[5,VertexLabels->"Name"];
AutomorphicGraphs[g2]


IsomorphicGraphQ[g2,#]&/@%


{True,True,True,True,True,True,True,True,True,True}