I have been interested in graph automorphism groups and I have a couple of questions about them that I was hoping people might be able to answer. I think I have seen other question which formatted similarly so I'm hoping this question is reasonable for this site.

1) Cayley's Theorem states that each graph with n nodes has an automorphism group which is a subgroup of $S_n$. For a graph with n nodes where n is the smallest possible number of nodes that allows a graph to have the automorphism group of the graph, are there ever more than 2 graphs? If so, can you provide a counter example?

2) Frucht's Theorem comments that every group G has a cayley graph which has G as its automorphism group and that any edge can be substituted for an asymmetric graph without changing G. I was curious if replacing the edge of a graph with a graph with a specific automorphism group yields a specific automorphism group? I kind of suspect that there is no formula for this or that it is extremely complex.

3) For a graph with an automorphism group G which is a non-simple group which has a normal subgroup N. Is there a significant meaning of N or G/N in relationship to the graph structure or the subgroups (and their automorphism groups)?

4) For a graph with a simple automorphism group G, does the fact the automorphism group is simple imply anything about the graphs structure or the subgroups (and their automorphism groups)?

  • 6
    $\begingroup$ One question per post, please. $\endgroup$ – bof Aug 14 '17 at 23:59
  • 2
    $\begingroup$ For 1. Yes, the graph $G$ and its complement. (Assuming $G$ is not isomorphic to its complement). $\endgroup$ – fidbc Aug 15 '17 at 1:43
  • $\begingroup$ @bof My bad. Sorry, I thought I had seen similar formats and I couldn't find that explicitly in the rules. Sorry $\endgroup$ – Sam H Aug 15 '17 at 2:11
  • $\begingroup$ @fidbc I was wondering whether there were ever any more than 2 graphs (which would be the graph itself and the complement) with the minimal amount of nodes for an automorphism group. $\endgroup$ – Sam H Aug 15 '17 at 2:13

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.