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.
No comments:
Post a Comment