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".