Thread: 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 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

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 be the union of n disjoint edges (on 2n vertices) and . Determine the order

I think the answer to this one was but I'm not sure how to get at that.

3) (Follow up to 2) Let in the preceding problem. Describe all the elements of order 3 in . 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.

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

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 be the union of n disjoint edges (on 2n vertices) and . Determine the order

I think the answer to this one was but I'm not sure how to get at that.

3) (Follow up to 2) Let in the preceding problem. Describe all the elements of order 3 in . 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?

Originally Posted by Drexel28

What is a graph automorphism?

This is what I have from my notes:
= {a ∈ , 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.

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 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 = { } and the set of vertices V = { }, where ={1,2}, = {3,4}, etc. Then we have n choices on where to put , n-1 choices on where to place 2 choices for , and 1 choice for . Also, for each edge we have 2 choices on how to arrange the two vertices. Thus .

3) Let the graph consist of 3 edges: ={1,2}, ={3,4}, and ={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.