# What can we say about the equivalence relation defined such that $G \sim H \Longleftrightarrow Aut(G) \simeq Aut(H)$?

Given two finite graphs $G, H$, I say that $G \sim H$ if and only if $Aut(G) \simeq Aut(H)$. We define $[G] = \{H \mid Aut(G) \simeq Aut(H) \}$ for any graph $G$. Due to theorems by Erdos and others we know that for random $G$ on $n$ vertices, $Pr(Aut(G) = K_1) \rightarrow 1$ as $n$ goes to infinity. I'm curious about other ways you can characterize $G \sim H$ which aren't obviously equivalent to this definition. For instance, for any class $[G]$, we note that there is some set of graphs $\bar{G_1}, ..., \bar{G_k}$ which have $n$ vertices where all other graphs in the class have more vertices. In particular, one has the complement of all of these graphs in this set as well. I'm curious if there may be some way to think of $[G]$ as a structure generated by these minimal graphs (or perhaps you need more than just these) and some set of operations.

There's a more restricted question I then can ask, which is for functions $f : Graph \rightarrow Graph$ such that $Aut(f(X)) = Aut(X)$. Can you completely classify such functions? I can reframe my original question by asking, for any given $G$, can I create a set $F$ where $\forall G' \in [G], G' = f_{i_l}(...f_{i_2}(f_{i_1}(\bar{G_i})))$ for some sequence $i_l$ and $f_i \in F$.

• "for random $G$, $|[G]| \to 2^{\binom n2}$..." I think you mean that with probability tending to $1$, $G \in [K_1]$, the equivalence class of graphs with trivial automorphism group. In general, $[G]$ should be infinite for any graph $G$. Nov 3, 2017 at 1:55
• Yeah that is what I meant, I will edit the question to reflect that Nov 3, 2017 at 2:35
• Do you mean for the functions $f$ to be graph homomorphisms? Nov 19, 2017 at 23:24
• Nope I don't @AlexanderGruber Nov 20, 2017 at 15:08