Mixing
![Sketch the sets in $mathbb C$ and determine whether they are open, closed, or neither; bounded; connected and their boundaries. [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Graphs Automorphisms
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Suppose we have a graph described by the adjacency matrix
beginalign*
beginbmatrix 0 & 1 & 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 1 & 0 & 1 \ 0 & 1 & 0 &0 & 1 & 0 endbmatrix.
endalign*
I'm trying to find all of the automorphisms of this graph. The identity mapping, clearly, is one. Also, the degree of vertices 1, 3, 4, and 6 is $2$, while the degrees of $2$ and $5$ is three. So, we can only map $2$ to itself or to $5$ and can only map $5$ to itself or to $2$. But, if we do that, to maintain the structure of the graph, we also need to swap $1$ and $4$. And, we can also make these two switches and swap $3$ and $6$, which have the same adjacencies, or simply switch $3$ and $6$ and change nothing else. I believe these are the only automorphisms of the graph, as any additional move requires altering connectedness in some way, e.g., swapping either $2$ or $5$, which essentially locks in the remaining moves.
So, I found that the automorphisms are:
beginalign*
& (1)(2)(3)(4)(5)(6) \
& (25)(14) \
& (36) \
& (25)(14)(36)
endalign*
If I work out the group table for this, I seem to be able to verify both closure under composition and inverses, so it seems that this qualifies as a group. But I can't help but feel that I missed something.
How does this look?
graph-theory automorphism-group
asked Jul 22 at 3:59
Matt.P
671313
add a comment |Â
up vote
2
down vote
favorite
Suppose we have a graph described by the adjacency matrix
beginalign*
beginbmatrix 0 & 1 & 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 1 & 0 & 1 \ 0 & 1 & 0 &0 & 1 & 0 endbmatrix.
endalign*
I'm trying to find all of the automorphisms of this graph. The identity mapping, clearly, is one. Also, the degree of vertices 1, 3, 4, and 6 is $2$, while the degrees of $2$ and $5$ is three. So, we can only map $2$ to itself or to $5$ and can only map $5$ to itself or to $2$. But, if we do that, to maintain the structure of the graph, we also need to swap $1$ and $4$. And, we can also make these two switches and swap $3$ and $6$, which have the same adjacencies, or simply switch $3$ and $6$ and change nothing else. I believe these are the only automorphisms of the graph, as any additional move requires altering connectedness in some way, e.g., swapping either $2$ or $5$, which essentially locks in the remaining moves.
So, I found that the automorphisms are:
beginalign*
& (1)(2)(3)(4)(5)(6) \
& (25)(14) \
& (36) \
& (25)(14)(36)
endalign*
If I work out the group table for this, I seem to be able to verify both closure under composition and inverses, so it seems that this qualifies as a group. But I can't help but feel that I missed something.
How does this look?
graph-theory automorphism-group
asked Jul 22 at 3:59
Matt.P
671313
1
The four maps you've written down certainly form a group, abstractly the Klein 4-group. I'd say you found everything.
– Gerry Myerson
Jul 22 at 4:11
2
Trying to find automorphisms by hand from looking at the adjacency matrix is probably the worst way to try to do it. Draw the graph.
– Morgan Rodgers
Jul 22 at 4:11
1
Looks fine to me. Those are all the automorphisms. Since there are only $6$ vertices and $7$ edges, it would also be easy to draw a picture of the graph, and you can see the automorphisms from the picture.
– bof
Jul 22 at 4:11
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Suppose we have a graph described by the adjacency matrix
beginalign*
beginbmatrix 0 & 1 & 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 1 & 0 & 1 \ 0 & 1 & 0 &0 & 1 & 0 endbmatrix.
endalign*
I'm trying to find all of the automorphisms of this graph. The identity mapping, clearly, is one. Also, the degree of vertices 1, 3, 4, and 6 is $2$, while the degrees of $2$ and $5$ is three. So, we can only map $2$ to itself or to $5$ and can only map $5$ to itself or to $2$. But, if we do that, to maintain the structure of the graph, we also need to swap $1$ and $4$. And, we can also make these two switches and swap $3$ and $6$, which have the same adjacencies, or simply switch $3$ and $6$ and change nothing else. I believe these are the only automorphisms of the graph, as any additional move requires altering connectedness in some way, e.g., swapping either $2$ or $5$, which essentially locks in the remaining moves.
So, I found that the automorphisms are:
beginalign*
& (1)(2)(3)(4)(5)(6) \
& (25)(14) \
& (36) \
& (25)(14)(36)
endalign*
If I work out the group table for this, I seem to be able to verify both closure under composition and inverses, so it seems that this qualifies as a group. But I can't help but feel that I missed something.
How does this look?
graph-theory automorphism-group
asked Jul 22 at 3:59
Matt.P
671313
Suppose we have a graph described by the adjacency matrix
beginalign*
beginbmatrix 0 & 1 & 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 & 0 & 1 \ 0 & 1 & 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 1 & 1 & 0 & 1 \ 0 & 1 & 0 &0 & 1 & 0 endbmatrix.
endalign*
I'm trying to find all of the automorphisms of this graph. The identity mapping, clearly, is one. Also, the degree of vertices 1, 3, 4, and 6 is $2$, while the degrees of $2$ and $5$ is three. So, we can only map $2$ to itself or to $5$ and can only map $5$ to itself or to $2$. But, if we do that, to maintain the structure of the graph, we also need to swap $1$ and $4$. And, we can also make these two switches and swap $3$ and $6$, which have the same adjacencies, or simply switch $3$ and $6$ and change nothing else. I believe these are the only automorphisms of the graph, as any additional move requires altering connectedness in some way, e.g., swapping either $2$ or $5$, which essentially locks in the remaining moves.
So, I found that the automorphisms are:
beginalign*
& (1)(2)(3)(4)(5)(6) \
& (25)(14) \
& (36) \
& (25)(14)(36)
endalign*
If I work out the group table for this, I seem to be able to verify both closure under composition and inverses, so it seems that this qualifies as a group. But I can't help but feel that I missed something.
How does this look?
graph-theory automorphism-group
asked Jul 22 at 3:59
Matt.P
671313
asked Jul 22 at 3:59
Matt.P
671313
asked Jul 22 at 3:59
Matt.P
671313
asked Jul 22 at 3:59
Matt.P
671313
671313
1
The four maps you've written down certainly form a group, abstractly the Klein 4-group. I'd say you found everything.
– Gerry Myerson
Jul 22 at 4:11
2
Trying to find automorphisms by hand from looking at the adjacency matrix is probably the worst way to try to do it. Draw the graph.
– Morgan Rodgers
Jul 22 at 4:11
1
Looks fine to me. Those are all the automorphisms. Since there are only $6$ vertices and $7$ edges, it would also be easy to draw a picture of the graph, and you can see the automorphisms from the picture.
– bof
Jul 22 at 4:11
add a comment |Â
1
The four maps you've written down certainly form a group, abstractly the Klein 4-group. I'd say you found everything.
– Gerry Myerson
Jul 22 at 4:11
2
Trying to find automorphisms by hand from looking at the adjacency matrix is probably the worst way to try to do it. Draw the graph.
– Morgan Rodgers
Jul 22 at 4:11
1
Looks fine to me. Those are all the automorphisms. Since there are only $6$ vertices and $7$ edges, it would also be easy to draw a picture of the graph, and you can see the automorphisms from the picture.
– bof
Jul 22 at 4:11
1
1
The four maps you've written down certainly form a group, abstractly the Klein 4-group. I'd say you found everything.
– Gerry Myerson
Jul 22 at 4:11
The four maps you've written down certainly form a group, abstractly the Klein 4-group. I'd say you found everything.
– Gerry Myerson
Jul 22 at 4:11
2
2
Trying to find automorphisms by hand from looking at the adjacency matrix is probably the worst way to try to do it. Draw the graph.
– Morgan Rodgers
Jul 22 at 4:11
Trying to find automorphisms by hand from looking at the adjacency matrix is probably the worst way to try to do it. Draw the graph.
– Morgan Rodgers
Jul 22 at 4:11
1
1
Looks fine to me. Those are all the automorphisms. Since there are only $6$ vertices and $7$ edges, it would also be easy to draw a picture of the graph, and you can see the automorphisms from the picture.
– bof
Jul 22 at 4:11
Looks fine to me. Those are all the automorphisms. Since there are only $6$ vertices and $7$ edges, it would also be easy to draw a picture of the graph, and you can see the automorphisms from the picture.
– bof
Jul 22 at 4:11
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
A good way to check your automorphisms is to draw the graph!
I have translated the adjacency matrix into a drawing by labelling the rows/columns as vertex 0, 1, 2, etc. Here we see that we have two choices for placing 1 and 4, which then determines where 0 and 3 are. After that, we have two choices for placing 2 and 5. So the graph has four automorphisms, and your list of them is correct.
answered Jul 22 at 4:09
Parcly Taxel
33.6k136588
Thank you! This is very helpful. I'm still very new to graph theory, so translating the matrix directly into a graph has been quite challenging. But, I agree this is quite useful.
– Matt.P
Jul 22 at 4:12
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
A good way to check your automorphisms is to draw the graph!
I have translated the adjacency matrix into a drawing by labelling the rows/columns as vertex 0, 1, 2, etc. Here we see that we have two choices for placing 1 and 4, which then determines where 0 and 3 are. After that, we have two choices for placing 2 and 5. So the graph has four automorphisms, and your list of them is correct.
answered Jul 22 at 4:09
Parcly Taxel
33.6k136588
Thank you! This is very helpful. I'm still very new to graph theory, so translating the matrix directly into a graph has been quite challenging. But, I agree this is quite useful.
– Matt.P
Jul 22 at 4:12
add a comment |Â
up vote
3
down vote
accepted
A good way to check your automorphisms is to draw the graph!
I have translated the adjacency matrix into a drawing by labelling the rows/columns as vertex 0, 1, 2, etc. Here we see that we have two choices for placing 1 and 4, which then determines where 0 and 3 are. After that, we have two choices for placing 2 and 5. So the graph has four automorphisms, and your list of them is correct.
answered Jul 22 at 4:09
Parcly Taxel
33.6k136588
Thank you! This is very helpful. I'm still very new to graph theory, so translating the matrix directly into a graph has been quite challenging. But, I agree this is quite useful.
– Matt.P
Jul 22 at 4:12
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
A good way to check your automorphisms is to draw the graph!
I have translated the adjacency matrix into a drawing by labelling the rows/columns as vertex 0, 1, 2, etc. Here we see that we have two choices for placing 1 and 4, which then determines where 0 and 3 are. After that, we have two choices for placing 2 and 5. So the graph has four automorphisms, and your list of them is correct.
answered Jul 22 at 4:09
Parcly Taxel
33.6k136588
A good way to check your automorphisms is to draw the graph!
I have translated the adjacency matrix into a drawing by labelling the rows/columns as vertex 0, 1, 2, etc. Here we see that we have two choices for placing 1 and 4, which then determines where 0 and 3 are. After that, we have two choices for placing 2 and 5. So the graph has four automorphisms, and your list of them is correct.
answered Jul 22 at 4:09
Parcly Taxel
33.6k136588
answered Jul 22 at 4:09
Parcly Taxel
33.6k136588
answered Jul 22 at 4:09
Parcly Taxel
33.6k136588
answered Jul 22 at 4:09
Parcly Taxel
33.6k136588
33.6k136588
Thank you! This is very helpful. I'm still very new to graph theory, so translating the matrix directly into a graph has been quite challenging. But, I agree this is quite useful.
– Matt.P
Jul 22 at 4:12
add a comment |Â
Thank you! This is very helpful. I'm still very new to graph theory, so translating the matrix directly into a graph has been quite challenging. But, I agree this is quite useful.
– Matt.P
Jul 22 at 4:12
Thank you! This is very helpful. I'm still very new to graph theory, so translating the matrix directly into a graph has been quite challenging. But, I agree this is quite useful.
– Matt.P
Jul 22 at 4:12
Thank you! This is very helpful. I'm still very new to graph theory, so translating the matrix directly into a graph has been quite challenging. But, I agree this is quite useful.
– Matt.P
Jul 22 at 4:12
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859079%2fgraphs-automorphisms%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
The four maps you've written down certainly form a group, abstractly the Klein 4-group. I'd say you found everything.
– Gerry Myerson
Jul 22 at 4:11
2
Trying to find automorphisms by hand from looking at the adjacency matrix is probably the worst way to try to do it. Draw the graph.
– Morgan Rodgers
Jul 22 at 4:11
1
Looks fine to me. Those are all the automorphisms. Since there are only $6$ vertices and $7$ edges, it would also be easy to draw a picture of the graph, and you can see the automorphisms from the picture.
– bof
Jul 22 at 4:11