Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.
Define a new graph $G_{Aut}$ with $V(G_{Aut})=G/{\sim}$ and there exists an edge $A-B$, for $A,B\in G/{\sim}$ iff there exists $a\in A$ and $b\in B$, such that $ab\in E(G)$.
Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.
I have two questions
$\cdot$ Does for every $G$ there exists $H$ such that $H_{Aut}\simeq G\ ?$ (I think the answer is YES)
$\cdot$ If so, how many vertices $H$ must have?
Best Answer
I also think that the answer to the first question is yes. Your note shows us that it is enough to consider graphs with non trivial automorphism group. If we can transform them in such a way, that we destroy all the initial (old) automorphisms, without creating vertices that can not be reached by new automorphisms. We are done. I think it can be done this way:
Consider the transformation which takes the $n$-dimensional hypercube to the $n+1$ dimensional one. (Or you can call it Cartesian product with $K_2$) We will do something similar. Take an exact copy of the initial graph $G$, and connect one vertex from each nontrivial orbit to its counterpart. In the resulting graph there will be no old automorphisms which can move them, since they can be moved only to each other, but they are from different orbits. We also did not create unreachable vertices since we can take every vertex to its counterpart and vice versa.
Iterating this procedure we can eliminate every old automorphism, but the number of vertices of the resulting graph grows exponentially with the number of transformations.
EDIT: If we take $n+1$ copies of $G$, and from every nontrivial old orbit, we chose a single vertex, and put a clicque on the vertices corresponding to the chosen one in the copies, then it is clear that the chosen vertices must map to each other.