Graph Automorphisms and Induced Subgraphs

206 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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 [1].

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.

[1] https://en.wikipedia.org/wiki/Reconstruction_conjecture