# How are graph automorphisms are affected by transformations?

I have a heavily symmetric regular graph whose automorphisms I know. I remove one subgraph and insert another one in a consistent manner; for example, this could be a Delta-Y transformation (replacing a node with a complete subgraph). I'd like to compute the automorphisms of the new graph using the automorphisms of the old graph.

I have the sense that this problem isn't too difficult, but am not sure how best to approach it and am new to algebraic graph theory.

What are some good references or suggested starting points?

-

I do not think there are any results that relate the automorphism group of a graph after subgraph replacement to the group of the original graph.

If the original graph was "heavily symmetric", you would expect the group of the new graph to be smaller - most local operations would destroy vertex transitivity, for example - but the details would depend on the operation.

I have the sense that this problem is extremely difficult. There are very few results in algebraic graph theory which determine the full automorphism group of a graph. There are results that describe the automorphism group of a graph product in terms of the automorphism groups of its factors. (See "Products Graphs" by Imrich and Klavsar, for example.)

-
Now consider an (undirected uncolored) Cayley graph $\Gamma$ of Aut(G). You can see that if we perform a delta-Y transformation in one of our gadgets, NONE of the original nontrivial automorphisms of $\Gamma$ remain, since the colored edge the gadget's standing in for couldn't stay in the same place. So depending on how your gadget is constructed, the new graph might have trivial automorphism group.