Skip to main content
2 of 2
added 271 characters in body

How dense is the set of asymmetric graphs?

On $n$ nodes, we have $2^{n(n-1)/2}$ graphs. Asymmetric graph is a graph that has only trivial automorphism. We known that asymptotically almost all finite graphs are asymmetric. Therefore, in the limit, the ratio of asymmetric graphs approaches 1.

However, I did not find any reference that provides lower bound on the number of asymmetric graphs on $n$ nodes. What is known about the density of asymmetric graphs as a function of the number of nodes $n$?

EDIT 1-3-2014 Thanks to both answers. I received two estimates of the number of symmetric graphs. I'm still hoping for a better tight asymptotic upper-bound such as $O(f(n))$ where $n= |V(G)|$ or even better a tight asymptotic lower-bound on the number of asymmetric graphs $\omega(g(n))$.