# Graph Automorphisms and Induced Subgraphs

Let $G=(V,E)$ be a finite simple graph, $\Gamma=Aut(G)$ be the automorphism group of $G$, and $G_v=G-\{v\}$ be a vertex-deleted induced subgraph of $G$. We define the following equivalence relation on the vertices,

$u,v\in V: u\sim v \iff G_u\cong G_v$

(I will forego proving that this is an equivalence as it seems trivial. If someone would like further clarification please let me know.) This equivalence partitions $V$ such that,

$V=\displaystyle\bigcup_{i=1}^k V_i$

We know that $u\sim v$ is a necessary condition for $u$ and $v$ to lie in the same orbit under $Aut(G)$ (i.e. these equivalence classes are larger than the orbits of $V$ under $\Gamma$).

Can we recover some information about $\Gamma$ given the equivalence classes under $\sim$?

It is clear that a partition of $V$ into orbits under $\Gamma$ will be a refinement of the partition. Also, we have an obvious upper bound $\Gamma\le S_{|V|}$. It seems that the "easier case" is when there are many vertices with distinct equivalence classes (i.e. the graph is not very symmetric).

• A first natural question in this direction is (analogous as for the orbits) whether almost all graphs have a trivial partition under $\sim$. If this is true (which I'd say it is) then there is not much you can say in general if you're given $\sim$ Nov 29, 2015 at 16:21
• @Joseph Zambrano: What do you mean by "some information"? Dou you have something specific in mind? What is the context of your question? Nov 29, 2015 at 16:43
• @Jernej Your assertion is almost certainly true (at least to me) but that still leaves "a lot" of graphs. Nov 29, 2015 at 18:51
• @Moritz Maybe I should clarify - if the partition is in fact the partition given by orbits then what can be said of $\Gamma$? If not, then is there a particular obstruction to the existence of an automorphism between two points which are equivalent under the relation? Nov 29, 2015 at 18:53

The multiset of isomorphisms types (equivalence classes in your question) induced by the removal of every single vertex is called the deck of $$G$$. Certainly, "some information" can be recovered from the deck. For example, in a number of special cases (classes of graphs), we know that $$G$$ can be reconstructed unambiguously from its deck. Thus, a fortiori, $$\Gamma$$ as well (from $$G$$). Whether this is true in general is not known and is referred to as the reconstruction conjecture .
In fact, the reconstruction conjecture is at least as strong as your question, since the reconstruction of $$G$$ yields that of $$\Gamma$$. Whether the converse holds is not clear to me (can we determine $$G$$ from $$\Gamma$$ and from the deck?). For sure, some information can be recovered from the deck that helps ruling out some automorphisms, e.g. the degree of every vertex and a few other such parameters are known to be determined unambiguously by the deck.