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$.