1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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$ $\endgroup$
    – Jernej
    Nov 29, 2015 at 16:21
  • $\begingroup$ @Joseph Zambrano: What do you mean by "some information"? Dou you have something specific in mind? What is the context of your question? $\endgroup$
    – Moritz
    Nov 29, 2015 at 16:43
  • $\begingroup$ @Jernej Your assertion is almost certainly true (at least to me) but that still leaves "a lot" of graphs. $\endgroup$
    – Joseph Zambrano
    Nov 29, 2015 at 18:51
  • $\begingroup$ @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? $\endgroup$
    – Joseph Zambrano
    Nov 29, 2015 at 18:53

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This question is quite old, but I believe to motivation behind it was exactly what you noted in your answer - "the reconstruction conjecture is at least as strong as your question". At the time I was looking at algebraic analogs of the reconstruction conjecture. Thanks for answering! $\endgroup$
    – Joseph Zambrano
    Jul 16, 2020 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .