Function Repository Resource:

AutomorphismGraph

Find an undirected graph whose automorphism group is isomorphic to the given group

Contributed by: Daniel McDonald

ResourceFunction["AutomorphismGraph"][g]

finds an undirected graph whose automorphism group is isomorphic to the group g.

Details

The Cayley graph of a group G with respect to some generating set S is a directed graph whose vertices are the elements of G, with an edge of color c_s directed from g to gs for each group element g∈G and generator s∈S. If C is the Cayley graph of G with respect to S, then G is isomorphic to the subgroup of the automorphism group of C consisting of the color-preserving automorphisms. An undirected graph H whose automorphism group is G can be constructed from C by replacing each edge of color c_s with an appropriate asymmetric graph H_s. Hence every finite group is isomorphic to the automorphism group of some undirected graph; this is the statement of Frucht’s theorem.

The group is typically a PermutationGroup or similar group like a SymmetricGroup, AlternatingGroup, CyclicGroup or DihedralGroup.