Is there a general strategy for identifying the automorphism group of a graph?

Question

I understand what an automorphism is, and I can sort of wrap my head around the idea that the set of automorphisms under composition form a group, but when asked to actually find the automorphism group of a graph, all I really know how to do is write out all the permutations then figure out which are automorphisms, which is both prohibitively tedious and gives answers as lists of permutations, instead of standard group notation.

Answer 1

I saw in the comments that you are stuck on the automorphism group of the cube graph and want a non-geometric approach. One way to show that the order of the automorphism group $G$ of the cube graph is $48$ is to use the orbit-stabilizer lemma and to draw the distance partition of the cube graph.

The cube graph is vertex-transitive, and so by the orbit-stabilizer lemma, $|G|= 8 \cdot |G_v|$, where $G_v$ is the set of automorphisms of the graph that fixes vertex $v$. Without loss of generality, take $v$ to be the identity vertex $000$ (I'm assuming you are familiar with this definition of the cube where the vertices correspond to bit strings of length $3$). Observe that any permutation of the three coordinates preserves adjacency and fixes $v$. This proves that $|G_v| \ge 3!=6$.

The distance partition of the cube graph with respect to vertex $v$ can be obtained by doing a breadth-first-search starting at vertex $v$. The $i$th layer of the distance partition is the set of vertices whose distance to $v$ is exactly $i$. It can be shown from this drawing of the cube graph that each vertex in the $ith$ layer ($i \ge 2$) has a unique set of neighbors in the previous layer. Hence, any automorphism of the graph which fixes $v$ and each of its neighbors is the trivial automorphism. This proves that $|G_v| \le 3!$. Hence $|G| = 8 \cdot 3! = 48$.

The above argument gives the order of the automorphism group. If you also want the structure of this group, it can be shown to be the semidirect product $\mathbb{Z}_2^3 \rtimes S_3$. The geometric approach can be used to show that the group is isomorphic to the direct product $C_2 \times S_4$.

The strategy used here to obtain the automorphism group was to observe that the cube graph can be defined equivalently by adjacencies between bit strings differing in exactly one coordinate and to use the basic theory of group actions. In the geometric approach also, one can consider the action of the automorphism group of the cube on its four diagonals.