Mixing
What is a simple to understand example (i.e. adjacency matrix) of a vertex transitive graph?
$begingroup$
I have a hard time understanding the intuition behind what a vertex transitive graph is. I was told that a circle graph on $10$ vertices is vertex transitive, but have been unable to generalize. The mathematical definition is unclear to me. Does anyone have a simple way of understanding it? Is there an example of an adjacency matrix representation of this?
graph-theory terminology adjacency-matrix
asked Aug 8 '17 at 1:27
user321627user321627
972515
$endgroup$
add a comment |
$begingroup$
I have a hard time understanding the intuition behind what a vertex transitive graph is. I was told that a circle graph on $10$ vertices is vertex transitive, but have been unable to generalize. The mathematical definition is unclear to me. Does anyone have a simple way of understanding it? Is there an example of an adjacency matrix representation of this?
graph-theory terminology adjacency-matrix
asked Aug 8 '17 at 1:27
user321627user321627
972515
$endgroup$
$begingroup$
You can't tell vertices apart, the graph looks the same standing on any of them? The $K_n$'s are examples. Looking at graphs that are not examples should also be useful. Examples of the latter could be graphs in which two vertices have different degrees.
$endgroup$
– Marja
Aug 8 '17 at 1:31
$begingroup$
Are you asking for a simple to understand example, or a simple to understand explanation? You ask for one in the title and the other in the body.
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
Also, what do you know about automorphism groups?
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
I am hoping to get an adjacency matrix representation of the vertices. Is there an example there?
$endgroup$
– user321627
Aug 8 '17 at 2:38
add a comment |
$begingroup$
I have a hard time understanding the intuition behind what a vertex transitive graph is. I was told that a circle graph on $10$ vertices is vertex transitive, but have been unable to generalize. The mathematical definition is unclear to me. Does anyone have a simple way of understanding it? Is there an example of an adjacency matrix representation of this?
graph-theory terminology adjacency-matrix
asked Aug 8 '17 at 1:27
user321627user321627
972515
$endgroup$
I have a hard time understanding the intuition behind what a vertex transitive graph is. I was told that a circle graph on $10$ vertices is vertex transitive, but have been unable to generalize. The mathematical definition is unclear to me. Does anyone have a simple way of understanding it? Is there an example of an adjacency matrix representation of this?
graph-theory terminology adjacency-matrix
graph-theory terminology adjacency-matrix
asked Aug 8 '17 at 1:27
user321627user321627
972515
asked Aug 8 '17 at 1:27
user321627user321627
972515
edited Aug 8 '17 at 2:38
user321627
asked Aug 8 '17 at 1:27
user321627user321627
972515
asked Aug 8 '17 at 1:27
user321627user321627
972515
asked Aug 8 '17 at 1:27
user321627user321627
972515
972515
$begingroup$
You can't tell vertices apart, the graph looks the same standing on any of them? The $K_n$'s are examples. Looking at graphs that are not examples should also be useful. Examples of the latter could be graphs in which two vertices have different degrees.
$endgroup$
– Marja
Aug 8 '17 at 1:31
$begingroup$
Are you asking for a simple to understand example, or a simple to understand explanation? You ask for one in the title and the other in the body.
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
Also, what do you know about automorphism groups?
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
I am hoping to get an adjacency matrix representation of the vertices. Is there an example there?
$endgroup$
– user321627
Aug 8 '17 at 2:38
add a comment |
$begingroup$
You can't tell vertices apart, the graph looks the same standing on any of them? The $K_n$'s are examples. Looking at graphs that are not examples should also be useful. Examples of the latter could be graphs in which two vertices have different degrees.
$endgroup$
– Marja
Aug 8 '17 at 1:31
$begingroup$
Are you asking for a simple to understand example, or a simple to understand explanation? You ask for one in the title and the other in the body.
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
Also, what do you know about automorphism groups?
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
I am hoping to get an adjacency matrix representation of the vertices. Is there an example there?
$endgroup$
– user321627
Aug 8 '17 at 2:38
$begingroup$
You can't tell vertices apart, the graph looks the same standing on any of them? The $K_n$'s are examples. Looking at graphs that are not examples should also be useful. Examples of the latter could be graphs in which two vertices have different degrees.
$endgroup$
– Marja
Aug 8 '17 at 1:31
$begingroup$
You can't tell vertices apart, the graph looks the same standing on any of them? The $K_n$'s are examples. Looking at graphs that are not examples should also be useful. Examples of the latter could be graphs in which two vertices have different degrees.
$endgroup$
– Marja
Aug 8 '17 at 1:31
$begingroup$
Are you asking for a simple to understand example, or a simple to understand explanation? You ask for one in the title and the other in the body.
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
Are you asking for a simple to understand example, or a simple to understand explanation? You ask for one in the title and the other in the body.
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
Also, what do you know about automorphism groups?
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
Also, what do you know about automorphism groups?
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
I am hoping to get an adjacency matrix representation of the vertices. Is there an example there?
$endgroup$
– user321627
Aug 8 '17 at 2:38
$begingroup$
I am hoping to get an adjacency matrix representation of the vertices. Is there an example there?
$endgroup$
– user321627
Aug 8 '17 at 2:38
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
In an effort to make the idea of vertex-transitivity more intuitive, I'll move through the formal definition with some comments, then give a few examples of graphs that are transitive, and a few that are not.
Automorphisms
The most important idea with any kind of transitivity is a graph automorphism. You probably know this, but I'll give a definition for completeness' sake.
For a graph $X$, an automorphism of $X$ is a bijective function $varphi: V(X)to V(X)$ which has the property that $x,yin V(X)$ are adjacent if and only if $varphi(x)$ and $varphi(y)$ are adjacent.
Intuitively, you can think of an automorphism as a symmetry the graph $X$ has. For example, you can label the circle graph on $10$ vertices with ${0,1,dots, 9}$ in order, going clockwise. An example of automorphism of this graph is $$varphi: C_{10}to C_{10} ~text{ where }~ imapsto i+1!!!!pmod{10}.$$ You can formally show that this is an automorphism, but an easy way to convince yourself of this is to see that $varphi$ is really just a rotation moving to the right by $2pi/10$. Similarly, the automorphism $psi: C_{10}to C_{10}$ given by $psi(i)=-i$ is the same as picking the graph up off the paper and flipping it over. A good exercise is to take the graph of a cube and find automorphisms of the graph by thinking about moving around a 3-D cube.
Vertex Transitivity
To apply this to vertex-transitivity, we first have the definition.
A graph $X$ is called transitive if for any pair of vertices $x,yin V(X)$ there is some automorphism $varphi$ such that $varphi(x) = y$.
What does this mean about the graph on an intuitive level? We can, as Marja does in the comments, think of it as saying that if you were to stand on any vertex and look out at the neighboring vertices, you wouldn't be able to tell which particular vertex you were on. In fact, it could be that you're on any vertex!
One consequence of this idea is that, at a minimum, a vertex-transitive graph must be $k$-regular, that is, all vertices must have degree $k$ for some integer $k$. In terms of the adjacency matrix, this means that the matrix has row sums equal to $k$, or that $k$ is an eigenvalue of the all-ones vector.
However, being regular and being transitive are not the same. This is because an automorphism, in a sense, 'picks up' the whole neighborhood of a vertex $x$ and moves them all together, so the neighborhood of every vertex must look exactly the same in the graph -- not just have the same size. This means that if some neighbor of $x$ has an important function in the graph (e.g. if you remove the neighbor the graph becomes disconnected), then the vertex you move it to has to have the same property.
Examples
To illustrate some of these ideas, here are a few examples. First, we have some examples of vertex-transitive graphs. Wolfram MathWorld has a good collection of small examples. Important classes of vertex-transitive graphs include
- Complete graphs
Circulant graphs (which are general cycle graphs)- Johnson graphs
with the Peterson graph and the Heawood graph being important specific examples. Graphs that are regular but not transitive are a little harder to come by, but there are definitely plenty. Examples include Tietze's graph, Frucht's graph, and a class of graphs called semisymmetric graphs, which the Folkman graph is an interesting example of.
Finally, there are many graphs which are not vertex-transitive. One important class of non-transitive graphs are trees (except $K_2$). In fact, almost all graphs are completely asymmetric, that is, they have no symmetry at all.
Edit: Somehow I blanked on adding Cayley graphs to the list of important vertex-transitive graphs. Doing exercises on Cayley graphs is a great way to gain intuition about what it means for the neighborhood of each vertex to 'look the same.'
answered Aug 8 '17 at 3:19
Santana AftonSantana Afton
2,9732629
$endgroup$
add a comment |
$begingroup$
Two people independently draw the same specific graph, one marks a node on this graph and tries to describe to the other what node has been marked.
Imagine trying this exercise with a friend using the 3 node path graph. The problem is symmetry, it's ok if you chose the middle node to mark otherwise there is no one answer but you can narrow it down.
Now try with the 4 node cycle graph. You'll find that whatever point you chose you cannot narrow it down at all, therefore this graph is vertex transitive.
vertex transitive graphs:
- You cannot describe a choice of any strict subset of nodes.
- extremely symmetric
- Every node has the same number of neighbours.
.
examples include:
- cycles
- complete graphs
- complete bipartite graphs
- Graphs of 2 nodes and fewer.
- Graphs of N dimensional platonic solids.
- Graphs of extruded polygons.
- A cycle, then additionally joining nodes N distance apart.
- the endless square grid
- the endless cubic grid
- the endless hexagonal grid
- Infinite trees where every node has N neighbours. This includes the infinite path.
- Cartesian (also called direct) product of vertex transitive graphs.
- Addition of a vertex transitive graph and itself.
answered Jan 26 at 15:27
alan2herealan2here
519219
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2386183%2fwhat-is-a-simple-to-understand-example-i-e-adjacency-matrix-of-a-vertex-trans%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In an effort to make the idea of vertex-transitivity more intuitive, I'll move through the formal definition with some comments, then give a few examples of graphs that are transitive, and a few that are not.
Automorphisms
The most important idea with any kind of transitivity is a graph automorphism. You probably know this, but I'll give a definition for completeness' sake.
For a graph $X$, an automorphism of $X$ is a bijective function $varphi: V(X)to V(X)$ which has the property that $x,yin V(X)$ are adjacent if and only if $varphi(x)$ and $varphi(y)$ are adjacent.
Intuitively, you can think of an automorphism as a symmetry the graph $X$ has. For example, you can label the circle graph on $10$ vertices with ${0,1,dots, 9}$ in order, going clockwise. An example of automorphism of this graph is $$varphi: C_{10}to C_{10} ~text{ where }~ imapsto i+1!!!!pmod{10}.$$ You can formally show that this is an automorphism, but an easy way to convince yourself of this is to see that $varphi$ is really just a rotation moving to the right by $2pi/10$. Similarly, the automorphism $psi: C_{10}to C_{10}$ given by $psi(i)=-i$ is the same as picking the graph up off the paper and flipping it over. A good exercise is to take the graph of a cube and find automorphisms of the graph by thinking about moving around a 3-D cube.
Vertex Transitivity
To apply this to vertex-transitivity, we first have the definition.
A graph $X$ is called transitive if for any pair of vertices $x,yin V(X)$ there is some automorphism $varphi$ such that $varphi(x) = y$.
What does this mean about the graph on an intuitive level? We can, as Marja does in the comments, think of it as saying that if you were to stand on any vertex and look out at the neighboring vertices, you wouldn't be able to tell which particular vertex you were on. In fact, it could be that you're on any vertex!
One consequence of this idea is that, at a minimum, a vertex-transitive graph must be $k$-regular, that is, all vertices must have degree $k$ for some integer $k$. In terms of the adjacency matrix, this means that the matrix has row sums equal to $k$, or that $k$ is an eigenvalue of the all-ones vector.
However, being regular and being transitive are not the same. This is because an automorphism, in a sense, 'picks up' the whole neighborhood of a vertex $x$ and moves them all together, so the neighborhood of every vertex must look exactly the same in the graph -- not just have the same size. This means that if some neighbor of $x$ has an important function in the graph (e.g. if you remove the neighbor the graph becomes disconnected), then the vertex you move it to has to have the same property.
Examples
To illustrate some of these ideas, here are a few examples. First, we have some examples of vertex-transitive graphs. Wolfram MathWorld has a good collection of small examples. Important classes of vertex-transitive graphs include
- Complete graphs
Circulant graphs (which are general cycle graphs)- Johnson graphs
with the Peterson graph and the Heawood graph being important specific examples. Graphs that are regular but not transitive are a little harder to come by, but there are definitely plenty. Examples include Tietze's graph, Frucht's graph, and a class of graphs called semisymmetric graphs, which the Folkman graph is an interesting example of.
Finally, there are many graphs which are not vertex-transitive. One important class of non-transitive graphs are trees (except $K_2$). In fact, almost all graphs are completely asymmetric, that is, they have no symmetry at all.
Edit: Somehow I blanked on adding Cayley graphs to the list of important vertex-transitive graphs. Doing exercises on Cayley graphs is a great way to gain intuition about what it means for the neighborhood of each vertex to 'look the same.'
answered Aug 8 '17 at 3:19
Santana AftonSantana Afton
2,9732629
$endgroup$
add a comment |
$begingroup$
In an effort to make the idea of vertex-transitivity more intuitive, I'll move through the formal definition with some comments, then give a few examples of graphs that are transitive, and a few that are not.
Automorphisms
The most important idea with any kind of transitivity is a graph automorphism. You probably know this, but I'll give a definition for completeness' sake.
For a graph $X$, an automorphism of $X$ is a bijective function $varphi: V(X)to V(X)$ which has the property that $x,yin V(X)$ are adjacent if and only if $varphi(x)$ and $varphi(y)$ are adjacent.
Intuitively, you can think of an automorphism as a symmetry the graph $X$ has. For example, you can label the circle graph on $10$ vertices with ${0,1,dots, 9}$ in order, going clockwise. An example of automorphism of this graph is $$varphi: C_{10}to C_{10} ~text{ where }~ imapsto i+1!!!!pmod{10}.$$ You can formally show that this is an automorphism, but an easy way to convince yourself of this is to see that $varphi$ is really just a rotation moving to the right by $2pi/10$. Similarly, the automorphism $psi: C_{10}to C_{10}$ given by $psi(i)=-i$ is the same as picking the graph up off the paper and flipping it over. A good exercise is to take the graph of a cube and find automorphisms of the graph by thinking about moving around a 3-D cube.
Vertex Transitivity
To apply this to vertex-transitivity, we first have the definition.
A graph $X$ is called transitive if for any pair of vertices $x,yin V(X)$ there is some automorphism $varphi$ such that $varphi(x) = y$.
What does this mean about the graph on an intuitive level? We can, as Marja does in the comments, think of it as saying that if you were to stand on any vertex and look out at the neighboring vertices, you wouldn't be able to tell which particular vertex you were on. In fact, it could be that you're on any vertex!
One consequence of this idea is that, at a minimum, a vertex-transitive graph must be $k$-regular, that is, all vertices must have degree $k$ for some integer $k$. In terms of the adjacency matrix, this means that the matrix has row sums equal to $k$, or that $k$ is an eigenvalue of the all-ones vector.
However, being regular and being transitive are not the same. This is because an automorphism, in a sense, 'picks up' the whole neighborhood of a vertex $x$ and moves them all together, so the neighborhood of every vertex must look exactly the same in the graph -- not just have the same size. This means that if some neighbor of $x$ has an important function in the graph (e.g. if you remove the neighbor the graph becomes disconnected), then the vertex you move it to has to have the same property.
Examples
To illustrate some of these ideas, here are a few examples. First, we have some examples of vertex-transitive graphs. Wolfram MathWorld has a good collection of small examples. Important classes of vertex-transitive graphs include
- Complete graphs
Circulant graphs (which are general cycle graphs)- Johnson graphs
with the Peterson graph and the Heawood graph being important specific examples. Graphs that are regular but not transitive are a little harder to come by, but there are definitely plenty. Examples include Tietze's graph, Frucht's graph, and a class of graphs called semisymmetric graphs, which the Folkman graph is an interesting example of.
Finally, there are many graphs which are not vertex-transitive. One important class of non-transitive graphs are trees (except $K_2$). In fact, almost all graphs are completely asymmetric, that is, they have no symmetry at all.
Edit: Somehow I blanked on adding Cayley graphs to the list of important vertex-transitive graphs. Doing exercises on Cayley graphs is a great way to gain intuition about what it means for the neighborhood of each vertex to 'look the same.'
answered Aug 8 '17 at 3:19
Santana AftonSantana Afton
2,9732629
$endgroup$
add a comment |
$begingroup$
In an effort to make the idea of vertex-transitivity more intuitive, I'll move through the formal definition with some comments, then give a few examples of graphs that are transitive, and a few that are not.
Automorphisms
The most important idea with any kind of transitivity is a graph automorphism. You probably know this, but I'll give a definition for completeness' sake.
For a graph $X$, an automorphism of $X$ is a bijective function $varphi: V(X)to V(X)$ which has the property that $x,yin V(X)$ are adjacent if and only if $varphi(x)$ and $varphi(y)$ are adjacent.
Intuitively, you can think of an automorphism as a symmetry the graph $X$ has. For example, you can label the circle graph on $10$ vertices with ${0,1,dots, 9}$ in order, going clockwise. An example of automorphism of this graph is $$varphi: C_{10}to C_{10} ~text{ where }~ imapsto i+1!!!!pmod{10}.$$ You can formally show that this is an automorphism, but an easy way to convince yourself of this is to see that $varphi$ is really just a rotation moving to the right by $2pi/10$. Similarly, the automorphism $psi: C_{10}to C_{10}$ given by $psi(i)=-i$ is the same as picking the graph up off the paper and flipping it over. A good exercise is to take the graph of a cube and find automorphisms of the graph by thinking about moving around a 3-D cube.
Vertex Transitivity
To apply this to vertex-transitivity, we first have the definition.
A graph $X$ is called transitive if for any pair of vertices $x,yin V(X)$ there is some automorphism $varphi$ such that $varphi(x) = y$.
What does this mean about the graph on an intuitive level? We can, as Marja does in the comments, think of it as saying that if you were to stand on any vertex and look out at the neighboring vertices, you wouldn't be able to tell which particular vertex you were on. In fact, it could be that you're on any vertex!
One consequence of this idea is that, at a minimum, a vertex-transitive graph must be $k$-regular, that is, all vertices must have degree $k$ for some integer $k$. In terms of the adjacency matrix, this means that the matrix has row sums equal to $k$, or that $k$ is an eigenvalue of the all-ones vector.
However, being regular and being transitive are not the same. This is because an automorphism, in a sense, 'picks up' the whole neighborhood of a vertex $x$ and moves them all together, so the neighborhood of every vertex must look exactly the same in the graph -- not just have the same size. This means that if some neighbor of $x$ has an important function in the graph (e.g. if you remove the neighbor the graph becomes disconnected), then the vertex you move it to has to have the same property.
Examples
To illustrate some of these ideas, here are a few examples. First, we have some examples of vertex-transitive graphs. Wolfram MathWorld has a good collection of small examples. Important classes of vertex-transitive graphs include
- Complete graphs
Circulant graphs (which are general cycle graphs)- Johnson graphs
with the Peterson graph and the Heawood graph being important specific examples. Graphs that are regular but not transitive are a little harder to come by, but there are definitely plenty. Examples include Tietze's graph, Frucht's graph, and a class of graphs called semisymmetric graphs, which the Folkman graph is an interesting example of.
Finally, there are many graphs which are not vertex-transitive. One important class of non-transitive graphs are trees (except $K_2$). In fact, almost all graphs are completely asymmetric, that is, they have no symmetry at all.
Edit: Somehow I blanked on adding Cayley graphs to the list of important vertex-transitive graphs. Doing exercises on Cayley graphs is a great way to gain intuition about what it means for the neighborhood of each vertex to 'look the same.'
answered Aug 8 '17 at 3:19
Santana AftonSantana Afton
2,9732629
$endgroup$
In an effort to make the idea of vertex-transitivity more intuitive, I'll move through the formal definition with some comments, then give a few examples of graphs that are transitive, and a few that are not.
Automorphisms
The most important idea with any kind of transitivity is a graph automorphism. You probably know this, but I'll give a definition for completeness' sake.
For a graph $X$, an automorphism of $X$ is a bijective function $varphi: V(X)to V(X)$ which has the property that $x,yin V(X)$ are adjacent if and only if $varphi(x)$ and $varphi(y)$ are adjacent.
Intuitively, you can think of an automorphism as a symmetry the graph $X$ has. For example, you can label the circle graph on $10$ vertices with ${0,1,dots, 9}$ in order, going clockwise. An example of automorphism of this graph is $$varphi: C_{10}to C_{10} ~text{ where }~ imapsto i+1!!!!pmod{10}.$$ You can formally show that this is an automorphism, but an easy way to convince yourself of this is to see that $varphi$ is really just a rotation moving to the right by $2pi/10$. Similarly, the automorphism $psi: C_{10}to C_{10}$ given by $psi(i)=-i$ is the same as picking the graph up off the paper and flipping it over. A good exercise is to take the graph of a cube and find automorphisms of the graph by thinking about moving around a 3-D cube.
Vertex Transitivity
To apply this to vertex-transitivity, we first have the definition.
A graph $X$ is called transitive if for any pair of vertices $x,yin V(X)$ there is some automorphism $varphi$ such that $varphi(x) = y$.
What does this mean about the graph on an intuitive level? We can, as Marja does in the comments, think of it as saying that if you were to stand on any vertex and look out at the neighboring vertices, you wouldn't be able to tell which particular vertex you were on. In fact, it could be that you're on any vertex!
One consequence of this idea is that, at a minimum, a vertex-transitive graph must be $k$-regular, that is, all vertices must have degree $k$ for some integer $k$. In terms of the adjacency matrix, this means that the matrix has row sums equal to $k$, or that $k$ is an eigenvalue of the all-ones vector.
However, being regular and being transitive are not the same. This is because an automorphism, in a sense, 'picks up' the whole neighborhood of a vertex $x$ and moves them all together, so the neighborhood of every vertex must look exactly the same in the graph -- not just have the same size. This means that if some neighbor of $x$ has an important function in the graph (e.g. if you remove the neighbor the graph becomes disconnected), then the vertex you move it to has to have the same property.
Examples
To illustrate some of these ideas, here are a few examples. First, we have some examples of vertex-transitive graphs. Wolfram MathWorld has a good collection of small examples. Important classes of vertex-transitive graphs include
- Complete graphs
Circulant graphs (which are general cycle graphs)- Johnson graphs
with the Peterson graph and the Heawood graph being important specific examples. Graphs that are regular but not transitive are a little harder to come by, but there are definitely plenty. Examples include Tietze's graph, Frucht's graph, and a class of graphs called semisymmetric graphs, which the Folkman graph is an interesting example of.
Finally, there are many graphs which are not vertex-transitive. One important class of non-transitive graphs are trees (except $K_2$). In fact, almost all graphs are completely asymmetric, that is, they have no symmetry at all.
Edit: Somehow I blanked on adding Cayley graphs to the list of important vertex-transitive graphs. Doing exercises on Cayley graphs is a great way to gain intuition about what it means for the neighborhood of each vertex to 'look the same.'
answered Aug 8 '17 at 3:19
Santana AftonSantana Afton
2,9732629
edited Dec 12 '17 at 19:26
answered Aug 8 '17 at 3:19
Santana AftonSantana Afton
2,9732629
answered Aug 8 '17 at 3:19
Santana AftonSantana Afton
2,9732629
answered Aug 8 '17 at 3:19
Santana AftonSantana Afton
2,9732629
2,9732629
add a comment |
add a comment |
$begingroup$
Two people independently draw the same specific graph, one marks a node on this graph and tries to describe to the other what node has been marked.
Imagine trying this exercise with a friend using the 3 node path graph. The problem is symmetry, it's ok if you chose the middle node to mark otherwise there is no one answer but you can narrow it down.
Now try with the 4 node cycle graph. You'll find that whatever point you chose you cannot narrow it down at all, therefore this graph is vertex transitive.
vertex transitive graphs:
- You cannot describe a choice of any strict subset of nodes.
- extremely symmetric
- Every node has the same number of neighbours.
.
examples include:
- cycles
- complete graphs
- complete bipartite graphs
- Graphs of 2 nodes and fewer.
- Graphs of N dimensional platonic solids.
- Graphs of extruded polygons.
- A cycle, then additionally joining nodes N distance apart.
- the endless square grid
- the endless cubic grid
- the endless hexagonal grid
- Infinite trees where every node has N neighbours. This includes the infinite path.
- Cartesian (also called direct) product of vertex transitive graphs.
- Addition of a vertex transitive graph and itself.
answered Jan 26 at 15:27
alan2herealan2here
519219
$endgroup$
add a comment |
$begingroup$
Two people independently draw the same specific graph, one marks a node on this graph and tries to describe to the other what node has been marked.
Imagine trying this exercise with a friend using the 3 node path graph. The problem is symmetry, it's ok if you chose the middle node to mark otherwise there is no one answer but you can narrow it down.
Now try with the 4 node cycle graph. You'll find that whatever point you chose you cannot narrow it down at all, therefore this graph is vertex transitive.
vertex transitive graphs:
- You cannot describe a choice of any strict subset of nodes.
- extremely symmetric
- Every node has the same number of neighbours.
.
examples include:
- cycles
- complete graphs
- complete bipartite graphs
- Graphs of 2 nodes and fewer.
- Graphs of N dimensional platonic solids.
- Graphs of extruded polygons.
- A cycle, then additionally joining nodes N distance apart.
- the endless square grid
- the endless cubic grid
- the endless hexagonal grid
- Infinite trees where every node has N neighbours. This includes the infinite path.
- Cartesian (also called direct) product of vertex transitive graphs.
- Addition of a vertex transitive graph and itself.
answered Jan 26 at 15:27
alan2herealan2here
519219
$endgroup$
add a comment |
$begingroup$
Two people independently draw the same specific graph, one marks a node on this graph and tries to describe to the other what node has been marked.
Imagine trying this exercise with a friend using the 3 node path graph. The problem is symmetry, it's ok if you chose the middle node to mark otherwise there is no one answer but you can narrow it down.
Now try with the 4 node cycle graph. You'll find that whatever point you chose you cannot narrow it down at all, therefore this graph is vertex transitive.
vertex transitive graphs:
- You cannot describe a choice of any strict subset of nodes.
- extremely symmetric
- Every node has the same number of neighbours.
.
examples include:
- cycles
- complete graphs
- complete bipartite graphs
- Graphs of 2 nodes and fewer.
- Graphs of N dimensional platonic solids.
- Graphs of extruded polygons.
- A cycle, then additionally joining nodes N distance apart.
- the endless square grid
- the endless cubic grid
- the endless hexagonal grid
- Infinite trees where every node has N neighbours. This includes the infinite path.
- Cartesian (also called direct) product of vertex transitive graphs.
- Addition of a vertex transitive graph and itself.
answered Jan 26 at 15:27
alan2herealan2here
519219
$endgroup$
Two people independently draw the same specific graph, one marks a node on this graph and tries to describe to the other what node has been marked.
Imagine trying this exercise with a friend using the 3 node path graph. The problem is symmetry, it's ok if you chose the middle node to mark otherwise there is no one answer but you can narrow it down.
Now try with the 4 node cycle graph. You'll find that whatever point you chose you cannot narrow it down at all, therefore this graph is vertex transitive.
vertex transitive graphs:
- You cannot describe a choice of any strict subset of nodes.
- extremely symmetric
- Every node has the same number of neighbours.
.
examples include:
- cycles
- complete graphs
- complete bipartite graphs
- Graphs of 2 nodes and fewer.
- Graphs of N dimensional platonic solids.
- Graphs of extruded polygons.
- A cycle, then additionally joining nodes N distance apart.
- the endless square grid
- the endless cubic grid
- the endless hexagonal grid
- Infinite trees where every node has N neighbours. This includes the infinite path.
- Cartesian (also called direct) product of vertex transitive graphs.
- Addition of a vertex transitive graph and itself.
answered Jan 26 at 15:27
alan2herealan2here
519219
edited Jan 26 at 15:43
answered Jan 26 at 15:27
alan2herealan2here
519219
answered Jan 26 at 15:27
alan2herealan2here
519219
answered Jan 26 at 15:27
alan2herealan2here
519219
519219
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2386183%2fwhat-is-a-simple-to-understand-example-i-e-adjacency-matrix-of-a-vertex-trans%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
You can't tell vertices apart, the graph looks the same standing on any of them? The $K_n$'s are examples. Looking at graphs that are not examples should also be useful. Examples of the latter could be graphs in which two vertices have different degrees.
$endgroup$
– Marja
Aug 8 '17 at 1:31
$begingroup$
Are you asking for a simple to understand example, or a simple to understand explanation? You ask for one in the title and the other in the body.
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
Also, what do you know about automorphism groups?
$endgroup$
– Morgan Rodgers
Aug 8 '17 at 1:55
$begingroup$
I am hoping to get an adjacency matrix representation of the vertices. Is there an example there?
$endgroup$
– user321627
Aug 8 '17 at 2:38