1
$\begingroup$

Let call a simple graph (not containing neither loops, nor multiple edges) "prime", if it has no non-trivial automorphisms, i.e. graph that has only "identity" automorphic transformation. I cannot find an example of prime graphs. Do they exist?

$\endgroup$
3
  • 2
    $\begingroup$ If I'm not mistaken, they're called asymmetric graphs: en.wikipedia.org/wiki/Asymmetric_graph According to this wikipedia page, the smallest nontrivial example is on 6 vertices, and there are infinitely many examples. Moreover, almost all graphs are asymmetric in the sense that the ratio of graphs with nontrivial automorphisms tends to zero as the number of vertices grow. $\endgroup$ Feb 15, 2015 at 11:47
  • $\begingroup$ I thought the term was rigid graph $\endgroup$ Feb 15, 2015 at 16:40
  • $\begingroup$ Thanks to Yuichiro Fujiwara and Benjamin Steinberg for their help! Wikipedia calls such graphs asymmetric, but Wolfram calls them rigid. I received answer to my question. $\endgroup$
    – Serg
    Feb 15, 2015 at 21:53

1 Answer 1

0
$\begingroup$

Frucht's theorem states that every finite group is the group of automorphisms of a finite undirected graph. The Frucht graph, is a $3$-regular graph whose automorphism group is the trivial group.

See http://en.wikipedia.org/wiki/Frucht%27s_theorem

$\endgroup$
1
  • $\begingroup$ Thanks to Pablo. It looks like almost all small graphs are symmetric. $\endgroup$
    – Serg
    Feb 15, 2015 at 21:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.