What is the most efficient algorithm to sample graphs with trivial automorphism groups ? Let us call a graph "asymmetric" if it has no nontrivial automorphism group. http://en.wikipedia.org/wiki/Asymmetric_graph



I'm looking for an efficient way to compute a random asymmetric graph on a given number of nodes.
Almost all graphs have trivial automorphism group. So all you need to do is generate a graph uniformly at random (see e.g. http://en.wikipedia.org/wiki/Random_graph), then compute its automorphism group (or just determine its order). Repeat until you find a graph with trivial automorphism group (also called a rigid graph).