How are graph automorphisms are affected by transformations?

Question

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?

Answer 1

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

Answer 2

I also have the sense that the problem is, in general, extremely hard. Actually, I'll give an example which hopefully will convince you that there's not a lot we can say, in general. (Unless you mean "symmetric" in the technical sense, to mean "arc-transitive," or really even "vertex-transitive," in which case my example breaks down, although it may well be possible to do something similar in those cases.) For concreteness, let's think about the delta-Y transformation.

There are certainly graphs with large automorphism group where you can perform a delta-Y tranformation and get back another graph with, um, large automorphism group. For instance, take a complete graph, or, if you're squeamish about the whole "it's not simple anymore" thing, subdivide each edge of a complete graph. But we'll take a higher level of abstraction and just say that Aut(G) is the automorphism group of our graph.

So if you're doing algebraic graph theory at all, you know about the Cayley graph of a group. The salient details here are just that it's got a vertex for each element of the group, a unique automorphism for each element corresponding to right multiplication, and no other automorphisms. The standard construction of the Cayley graph is directed and has edges assigned to color classes, but there's a combinatorial trick to make a "vanilla" Cayley graph, which is to attach little gadgets to your edges to indicate color and direction. This graph is no longer vertex-transitive, which sucks, but its automorphism group is still completely described (at least if you're careful about building your gadgets...)

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.