Maximum size of the automorphism group of a graph given some constraint?

Question

Are there any results on the maximum size of the automorphism group of a graph with $n$ vertices and $m$ edges? What about for a graph with $n$ vertices and is $d$-regular?

Answer 1

For your second question, Wormald, On the number of automorphisms of a regular graph proves an upper bound for connected $d$-regular graphs; there's a complicated expression which implies in particular that for connected $3$-regular graphs the number of automorphisms is at most $3n2^n$.

Without looking too closely at the bound for $d=3$ or in general, we can notice that it's at most exponential, and so if you don't care if your graph is connected, we can do better by having around $\frac n{d+1}$ copies of $K_{d+1}$. Then the number of automorphisms is roughly $(\frac{n}{d+1})! (d+1)!^{n/(d+1)}$, which grows much faster than exponential. This is likely to be best possible.

For a lower bound in the $m$-edge case, note that $K_{k,n-k}$ has $k(n-k)$ edges and $k!(n-k)!$ automorphisms, which is really close to $n!$ when $k$ is small.