8
$\begingroup$

Hi, this is my 2nd question in this site. If it is not up to the mark, please do let me know, I will surely try to improve.

The problem is from Graph Theory, specially Automorphism Group. I know that the Automorphism Group of the complement of the complete graph $\overline{K}_n$ is isomorphic to $S_n$, the symmetric group on $n$ symbols.

Also the Automorphism Group of the path graph $P_4$ will be $\{I,(1,4)(2,3\}$ which isomorphic to $S_2$.

enter image description here

My problem is a bit tricky where I am stuck:

Problem: Let $G$ be a graph such that $G$ is made of $4$ components $G_1,G_2,G_3,G_4$ where $G_1=\overline{K}_2,G_2=\overline{K}_3,G_3=\overline{K}_4,G_4=\overline{K}_5$, i.e. $G$ can be obtained from $P_4$ in the following way:

The vertex 1 in $P_4$ is replaced by $G_1=\overline{K}_2$, the vertex 2 in $P_4$ is replaced by $G_2=\overline{K}_3$, the vertex 3 in $P_4$ is replaced by $G_3=\overline{K}_4$, the vertex 4 in $P_4$ is replaced by $G_4=\overline{K}_5$. All the vertices of $\overline{K}_2$ are adjacent to all the vertices of $\overline{K}_3$, all the vertices of $\overline{K}_3$ are adjacent to all the vertices of $\overline{K}_4$, and all the vertices of $\overline{K}_4$ are adjacent to all the vertices of $\overline{K}_5$.

Find the automorphism group of $G$ and its order.

My try: I understand that the automorphism group of $G_1$ is isomorphic to $S_2$,
the automorphism group of $G_2$ is isomorphic to $S_3$, the automorphism group of $G_3$ is isomorphic to $S_4$, and the automorphism group of $G_4$ is isomorphic to $S_5$. Also the automorphism group of $P_4$ is isomorphic to $S_2$. I also understand that the blocks $G_1,G_2,G_3,G_4$ follow the adjacency criterion as in $P_4$.

But I am stuck on how to find the automorphism group of $G$ from here. I require some help from you all. I am looking forward to some responses from all the learned experts available in MSE.

$\endgroup$

1 Answer 1

5
$\begingroup$

The vertices in $G_1,G_2,G_3,G_4$ are characterized by having degrees $3,6,8,4$, respectively. Hence any automorphism must permute vertices only within each $G_i$. This makes the automorphism group a subgroup of $S_2\times S_3\times S_4\times S_5$. On the other hand, any permutation of $G_1$ alone (or $G_2$ alone or …) turns out to be an automorphism, hence the group is indeed $S_2\times S_3\times S_4\times S_5$.

$\endgroup$
0

You must log in to answer this question.

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