Testing isomorphism of asymmetric graphs While reading the question Examples where the uniqueness of the solution makes it easier to find, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) problem is in $P$.


But what happens if we assume that both $G_1$ and $G_2$ are asymmetric (i.e. both have only the trivial (identity) automorphism) ? Does the problem become easier (polynomial time)? 


Note: the problem cannot be harder than Graph Automorphism ($GA$), because there is a quick reduction: just use $GA$ on $G_1 \cup G_2$, if the answer is yes then the two graphs are isomorphic (see also Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. 401-411).
Upon request of Marzio De Biasi I'm converting my comment into an answer.

A graph is asymmetric (some authors refer to it as rigid) if it has a unique automorphism, i.e., the identity. As pointed out by Chad Brewbacker, most graphs are asymmetric. However the following two questions are open:

1) Is isomorphism of asymmetric graphs in P? 

2) Can isomorphism of general graphs be reduced to isomorphism of asymmetric graphs?

Question 1) has received a lot of attention in quantum computing due to the fact that the isomorphism of asymetric graphs can be reduced to the nonabelian hidden subgroup problem  and to the non abelian hidden shift problem. However the results are negative, showing that one needs to prepare at least $\Omega(n\log n)$ hidden subgroup states or hidden shift states to have enough information to solve the isomorphism problem.