# Graph Automorphisms

• Mar 28th 2010, 06:19 PM
moocow
Graph Automorphisms
EDIT: I think I got it now. (see 4th post)

Hello. I recently had an Algebra exam that had a few questions about graph automorphisms. I'm not too familiar with graphs (a little bit familiar with permutations, groups, and morphisms though) so I was hoping someone could help me out with these questions and/or maybe lead me to any online resources about the subject since my textbook doesn't say much about it.

1) Let \$\displaystyle T\$ be the graph on 4 vertices with edges {1,2} and {3,4} (union of two disjoint edges). Make a list of all elements in the automorphism group of \$\displaystyle T\$

This one seems easiest, so if someone could explain how to go about this maybe I would understand the concept a bit better and try figuring out the other two.

2) Let \$\displaystyle T_n\$ be the union of n disjoint edges (on 2n vertices) and \$\displaystyle G_n = Aut(T_n)\$. Determine the order \$\displaystyle |G_n|\$

I think the answer to this one was \$\displaystyle n!*2^n\$ but I'm not sure how to get at that.

3) (Follow up to 2) Let \$\displaystyle G=G_3\$ in the preceding problem. Describe all the elements of order 3 in \$\displaystyle G_3\$. How many are there?

Again on this one I know the answer is 8 elements of order 3, but have no idea how to find that. The elements are listed as permutations and I know the elements of order three are products of disjoint 3 cycles, but I don't know how to find them.

I'd greatly appreciate any help, since I'm not really familiar with graphs at all.
• Mar 28th 2010, 06:59 PM
Drexel28
Quote:

Originally Posted by moocow
Hello. I recently had an Algebra exam that had a few questions about graph automorphisms. I'm not too familiar with graphs (a little bit familiar with permutations, groups, and morphisms though) so I was hoping someone could help me out with these questions and/or maybe lead me to any online resources about the subject since my textbook doesn't say much about it.

1) Let \$\displaystyle T\$ be the graph on 4 vertices with edges {1,2} and {3,4} (union of two disjoint edges). Make a list of all elements in the automorphism group of \$\displaystyle T\$

This one seems easiest, so if someone could explain how to go about this maybe I would understand the concept a bit better and try figuring out the other two.

2) Let \$\displaystyle T_n\$ be the union of n disjoint edges (on 2n vertices) and \$\displaystyle G_n = Aut(T_n)\$. Determine the order \$\displaystyle |G_n|\$

I think the answer to this one was \$\displaystyle n!*2^n\$ but I'm not sure how to get at that.

3) (Follow up to 2) Let \$\displaystyle G=G_3\$ in the preceding problem. Describe all the elements of order 3 in \$\displaystyle G_3\$. How many are there?

Again on this one I know the answer is 8 elements of order 3, but have no idea how to find that. The elements are listed as permutations and I know the elements of order three are products of disjoint 3 cycles, but I don't know how to find them.

I'd greatly appreciate any help, since I'm not really familiar with graphs at all.

What is a graph automorphism?
• Mar 28th 2010, 07:05 PM
moocow
Quote:

Originally Posted by Drexel28
What is a graph automorphism?

This is what I have from my notes:
\$\displaystyle G = Aut(T)\$ = {a ∈ \$\displaystyle S_v\$, a(m) ∈ E ∀ m ∈ E}

Where a is a permutation, V is the set of vertices, and E is the set of edges.

edit: As an example we considered a square (union of 4 edges), which I thought was a bit easier to understand since you could just look at the rotation and reflection symmetries. I just can't really visualize a similar way to list the elements for a graph with disjoint edges.
• Mar 29th 2010, 12:54 PM
moocow
Well, after staring at the problems for quite some time today I think I've got them figured out. Thanks for anybody who took the time to look at this.

The key thing is that \$\displaystyle Aut(T)\$ maps edges to edges, so any two particular vertices have to get mapped to the same edge (paired vertices can't be separated in the mapping, they both have to go to the same edge if they started on the same edge). I found it helped a lot to actually draw some of this stuff out on paper, but if anyone is interested here is what I came up with for solutions:

1) The elements (permutations) are: (1 2), (1 2)(3 4), (1 3)(2 4), (1 3 2 4), (1 4)(2 3), (1 4 2 3), and (3 4).

2) Let the set of edges E = {\$\displaystyle e_1, e_2, ... , e_n\$} and the set of vertices V = {\$\displaystyle 1, 2, 3, ..., 2n-1, 2n\$}, where \$\displaystyle e_1\$={1,2}, \$\displaystyle e_2\$ = {3,4}, etc. Then we have n choices on where to put \$\displaystyle e_1\$, n-1 choices on where to place \$\displaystyle e_2,...,\$2 choices for \$\displaystyle e_n-1\$, and 1 choice for \$\displaystyle e_n\$. Also, for each edge we have 2 choices on how to arrange the two vertices. Thus \$\displaystyle |Aut(T_n)|=n!*2^n\$.

3) Let the graph consist of 3 edges: \$\displaystyle e_1\$={1,2}, \$\displaystyle e_2\$={3,4}, and \$\displaystyle e_3\$={5,6}. The elements (permutations) of of order 3 are products of disjoint 3 cycles. Therefore, since vertices have to "stick together", we can't map 1 to 2 because then we'd have to map 2 to 1 and we'd have a 2-cycle (1 2) in the permutation.

Starting with 1, we can map it to any of 3, 4, 5, or 6. Say we map it to 3 - then we know 2 has to map to 4 since 1 & 2 have to stay on the same edge. We also can't map 3 back to 1 (then it would be a 2 cycle) or 2 (then it would be a 4 cycle: (1 3 2 4)). Thus we can map 3 to either 5 or 6. If we map 3 to 5 then for it to be a 3 cycle, 5 goes back to 1. So we have a 3 cycle (1 3 5) - then we map 2 to the same edge as 1, since 1 is mapped to 3 we map 2 to 4. 4 has to go to the same edge as 3 (which is mapped to 5) so we map 4 to 6. Finally, we check that 6 maps back to 2 to complete the 3 cycle, which indeed it does (since 5 was mapped to 1). Therefore we have an element (1 3 5)(2 4 6).

Repeating the same line of reasoning got me in total 8 elements of order 3: (1 3 5)(2 4 6), (1 3 6)(2 4 5), (1 4 5)(2 3 6), (1 4 6)(2 3 5), (1 5 3)(2 6 4), (1 5 4)(2 6 3), (1 6 3)(2 5 4), (1 6 4)(2 5 3). Again, this is MUCH easier to see if you actually draw out the graph.

If anybody has any questions about my reasoning, or sees anything wrong feel free to let me know. Otherwise I think I understand it now. Thanks again for anybody who looked at it. Cheers. (Rock)