While most graphs have trivial aut group (https://www.sciencedirect.com/science/article/pii/S0012365X08006900, https://users.renyi.hu/~p_erdos/1963-04.pdf, and also from sage simulations), I am interested in undirected graph families which have large aut groups (preferably exponential in the number of vertices).
Circulant graphs are one example of a graph family which have a non trivial aut group. (They contain the n-cycle), but I am not sure what conditions they need to satisfy for the aut group to be larger than n. (perhaps related to the spectrum of the graph)
I am wondering if there exist infinite families of graphs with large aut group, or methods to construct graphs of a given degree with large aut group. (rather than just isolated examples like the complete graph and the discrete graph)
2026-03-27 23:30:41.1774654241
Graphs with large automorphism groups
267 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
A good place to look might be families of graphs that are created to test graph isomorphism algorithms. For example, this paper (Benchmark Graphs for Practical Graph Isomorphism) describes the Cai-Fürer Immerman gadgets and Miyazaki graphs.
If you need actual examples of such graphs, it might be convenient to download them from the Nauty/Traces website here, although they may be in other databases of graphs elsewhere.