For a graph G with n nodes and a non-trivial automorphism group, is there a way to tell how many other graphs with n nodes and the same automorphism groups exist?

Obviously most graphs will have a complement with the same automorphism group(except the graphs whose complement is the graph).

I know that for larger graphs most of them are asymmetric and those may have many other graphs with identical automorphism groups. I am pretty sure that the complete graph and the empty graph are the only two graphs with n nodes that have the symmetric group on n letters as their automorphism group.

  • $\begingroup$ No, there is no way to tell without finding all of them (except for in a few special cases). There is no way to predict, there may be very few or very many depending on $n$ and on the group. $\endgroup$ – Morgan Rodgers Aug 6 '17 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.