Testing isomorphism of asymmetric graphs
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.