-2
$\begingroup$

Let $F$ be some function graph to graph which preserve graph isomorphism.

Example of such $F$ are the line graph, the $k$-subdivision of $G$ and many others.

$F$ need not preserve the order, the degree sequence, the girth, the size of the maximum independent set and others.

Q1 Must all $F$ preserve the order of the automorphism group?

According to my limited experiments, the answer is positive.

Added: In comments Brendan McKay suggested counterexample for the subdivision transformation and it is the cycle graph.

According to my experiments (modulo errors), subdividing a non-rigid graphs preserves the order of the automorphism group.

Q2 How to explain this observation?

Some tested subdivision examples from sagemath and the "nauty and traces" database:

PetersenGrap, PaleyGraph(73), SRG_100_44_18_20, "had-20" of order 80, "sts-21" of order 70.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ In addition to Martti's example, subdivision does not preserve automorphism group. Consider subdividing a cycle. $\endgroup$
    – Brendan McKay
    Commented Jul 1, 2023 at 14:23
  • $\begingroup$ @BrendanMcKay Thanks, you are right. $\endgroup$
    – joro
    Commented Jul 1, 2023 at 14:40
  • $\begingroup$ @BrendanMcKay Is it coincidence that subdividing random/selected non-rigid graphs preserves the automorphism group? $\endgroup$
    – joro
    Commented Jul 1, 2023 at 15:44
  • 1
    $\begingroup$ The line graph functor also does not preserve the automorphism group. For example, $L(K_4)$ is the complement of $K_2 \sqcup K_2 \sqcup K_2$, which has automorphism group $C_2^3 \rtimes S_3$, of order $48$. $\endgroup$
    – Sean Eberhard
    Commented Jul 2, 2023 at 18:57
  • 1
    $\begingroup$ Although Q1 itself was too naive, it seems to be a source of somewhat interesting questions to take a given injective functor $F$ from graphs to graphs and ask for which graphs $F:\operatorname{Aut}(G) \to \operatorname{Aut}(F(G))$ fails to be an isomorphism. $\endgroup$
    – Sean Eberhard
    Commented Jul 2, 2023 at 19:13

2 Answers 2

Reset to default
5
$\begingroup$

This is an answer to the follow-up question about automorphisms of a subdivision.

Suppose $G$ is a connected graph which is not $2$-regular. Let $G^{(k)}$ be the $k$-subdivision of $G$, i.e., the graph obtained by replacing each edge with a path of length $k$. Then $\operatorname{Aut}(G^{(k)}) \cong \mathrm{Aut}(G)$.

Proof: Clearly every automorphism of $G$ uniquely extends to $G^{(k)}$. Conversely, let $\alpha \in \mathrm{Aut}(G^{(k)})$ and let $v_0 \in V(G) \subseteq V(G^{(k)})$ be a vertex of degree $d(v_0) \ne 2$. Since the vertices introduced by subdivision all have degree $2$, $\alpha(v_0)$ must again be a vertex of $G$. Since the vertices of $G$ are precisely those such that $d_{G^{(k)}}(v,v_0)$ is divisible by $k$, $\alpha$ preserves $V(G)$ and induces an automorphism of $G$ (whose unique extension is $\alpha$).

So subdivision can introduce automorphisms only if $G$ has a connected component which is $2$-regular, i.e., either a finite cycle or a bi-infinite path.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. I am not good at group theory, but doesn't this construction gives infinitely many groups of given order? (The orders of $G$ and $G^k$ are different). $\endgroup$
    – joro
    Commented Jul 2, 2023 at 13:58
  • 2
    $\begingroup$ @joro They are only different as permutation groups. As abstract groups they are the same. For any abstract group there are infinitely many permutation representations, that's all. $\endgroup$
    – Brendan McKay
    Commented Jul 2, 2023 at 14:05
3
$\begingroup$

If you send a graph to two disjoint copies of the same graph, you get a transformation sending isomorphic graphs to isomorphic graphs (in fact, you get an endofunctor on the category of graphs), but this does not preserve the order of the automorphism group.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, this works. $\endgroup$
    – joro
    Commented Jul 1, 2023 at 13:19

You must log in to answer this question.

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