For a Graph G, I am trying to understand how the automorphism of G is equivalent to the automorphism of the complement of G.

I understand that an automorphism is an isomorphism of G onto itself. This, in fact, seems like it should be a fairly basic concept and so my confusion is likely in relation to what abstract concept an automorphism actually manifests as, and therefore how the equivalency can be seen.

  • 2
    $\begingroup$ What is the complement of a group? Do you mean the opposite group? $\endgroup$
    – Thorgott
    Mar 31 '20 at 22:49
  • 3
    $\begingroup$ @Thorgott I think $G$ is a graph. $\endgroup$
    – Arthur
    Mar 31 '20 at 22:57

Because $$(f(i),f(j))\in E(G) \iff (i,j)\in E(G)$$ is equivalent to $$(f(i),f(j))\not\in E(G) \iff (i,j)\not\in E(G),$$ which is equivalent to $$(f(i),f(j))\in E(\overline{G}) \iff (i,j)\in E(\overline{G}).$$

  • $\begingroup$ Thank you, that is very helpful! I am still having trouble imagining a visual example of this using graphs, if you have any good ideas where I could look for such? $\endgroup$
    – JFreeman
    Mar 31 '20 at 23:15
  • $\begingroup$ Another helpful thought for me is that automorphisms preserve adjacencies and hence non-adjacencies. That's an easy way to think about this concept. $\endgroup$
    – JFreeman
    Apr 20 '20 at 9:21

Your Answer

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

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