Number of Automorphisms of a graph for graph isomorphism Let $G$ and $H$ be two $r$-regular connected graphs of size $n$.
Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. 
If $G=H$ then $A$ is the set of automorphisms of $G$.


  What is the best known upper-bound on the size of of $A$?
  Are there any results for particular graph classes (not containing complete/cycle graphs)? 




Note: 
Constructing the automorphism group is at least as difficult 
(in terms of its computational complexity) as solving the graph isomorphism problem. 
In fact, just counting the automorphisms is polynomial-time equivalent to 
graph isomorphism, c.f. R. Mathon, "A note on the graph isomorphism counting problem".
Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-bound for the $3$-regular case. Maybe there are results in this line for general $k$-regular graphs.

For a lower bound, consider formula $F$ with $n$ inputs whose gates are addition $\mod k$ gates of fan-in 2.  Then using a resut of Toran one can construct a $k$-regular graph $G(F)$ with $O(k^2\cdot n)$ vertices whose automorphism group encodes all possible evaluations of $F$. This implies that the number of automorphisms of
$G(F)$ is at least $k^n$. This shows that the there is an exponential lower bound for the number of automorphisms of $k$-regular graphs in function of its number of vertices.