What does “Vertex-transitivity” tell us about an arbitrary graph?
$begingroup$
I know the formal definition, i.e. , for any arbitrary graph G,
$forall v_i,v_jin V(G), exists g in Auto(G) , s.t. g(v_i)=v_j$
But what does it mean in a broader sense?
graph-theory
$endgroup$
add a comment |
$begingroup$
I know the formal definition, i.e. , for any arbitrary graph G,
$forall v_i,v_jin V(G), exists g in Auto(G) , s.t. g(v_i)=v_j$
But what does it mean in a broader sense?
graph-theory
$endgroup$
3
$begingroup$
It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
$endgroup$
– Théophile
Nov 25 '16 at 21:11
$begingroup$
So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
$endgroup$
– Ashkan Ranjbar
Nov 25 '16 at 22:10
$begingroup$
Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
$endgroup$
– Théophile
Nov 26 '16 at 2:06
$begingroup$
Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
$endgroup$
– Théophile
Nov 26 '16 at 2:09
add a comment |
$begingroup$
I know the formal definition, i.e. , for any arbitrary graph G,
$forall v_i,v_jin V(G), exists g in Auto(G) , s.t. g(v_i)=v_j$
But what does it mean in a broader sense?
graph-theory
$endgroup$
I know the formal definition, i.e. , for any arbitrary graph G,
$forall v_i,v_jin V(G), exists g in Auto(G) , s.t. g(v_i)=v_j$
But what does it mean in a broader sense?
graph-theory
graph-theory
asked Nov 25 '16 at 20:58


Ashkan RanjbarAshkan Ranjbar
11713
11713
3
$begingroup$
It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
$endgroup$
– Théophile
Nov 25 '16 at 21:11
$begingroup$
So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
$endgroup$
– Ashkan Ranjbar
Nov 25 '16 at 22:10
$begingroup$
Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
$endgroup$
– Théophile
Nov 26 '16 at 2:06
$begingroup$
Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
$endgroup$
– Théophile
Nov 26 '16 at 2:09
add a comment |
3
$begingroup$
It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
$endgroup$
– Théophile
Nov 25 '16 at 21:11
$begingroup$
So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
$endgroup$
– Ashkan Ranjbar
Nov 25 '16 at 22:10
$begingroup$
Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
$endgroup$
– Théophile
Nov 26 '16 at 2:06
$begingroup$
Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
$endgroup$
– Théophile
Nov 26 '16 at 2:09
3
3
$begingroup$
It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
$endgroup$
– Théophile
Nov 25 '16 at 21:11
$begingroup$
It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
$endgroup$
– Théophile
Nov 25 '16 at 21:11
$begingroup$
So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
$endgroup$
– Ashkan Ranjbar
Nov 25 '16 at 22:10
$begingroup$
So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
$endgroup$
– Ashkan Ranjbar
Nov 25 '16 at 22:10
$begingroup$
Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
$endgroup$
– Théophile
Nov 26 '16 at 2:06
$begingroup$
Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
$endgroup$
– Théophile
Nov 26 '16 at 2:06
$begingroup$
Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
$endgroup$
– Théophile
Nov 26 '16 at 2:09
$begingroup$
Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
$endgroup$
– Théophile
Nov 26 '16 at 2:09
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.
- Graph $X$ is regular.(converse is not true Eg: Frucht Graph)
- $Aut(X)$ is non-trivial.
- Graph $X$ is symmetric.
- Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.
For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.
Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.
$endgroup$
add a comment |
$begingroup$
Its very similar to what homogeneity means in topological spaces.
Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.
$endgroup$
add a comment |
$begingroup$
Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.
Graphs can be used to show group structure, for example:
This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.
Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.
Moving the identity element e
on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab
is still e
, it's all still the same object.
$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%2f2030701%2fwhat-does-vertex-transitivity-tell-us-about-an-arbitrary-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.
- Graph $X$ is regular.(converse is not true Eg: Frucht Graph)
- $Aut(X)$ is non-trivial.
- Graph $X$ is symmetric.
- Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.
For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.
Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.
$endgroup$
add a comment |
$begingroup$
If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.
- Graph $X$ is regular.(converse is not true Eg: Frucht Graph)
- $Aut(X)$ is non-trivial.
- Graph $X$ is symmetric.
- Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.
For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.
Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.
$endgroup$
add a comment |
$begingroup$
If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.
- Graph $X$ is regular.(converse is not true Eg: Frucht Graph)
- $Aut(X)$ is non-trivial.
- Graph $X$ is symmetric.
- Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.
For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.
Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.
$endgroup$
If a graph $X=(V(X),E(X))$ is vertex transitive, then we can talk about some obvious things.
- Graph $X$ is regular.(converse is not true Eg: Frucht Graph)
- $Aut(X)$ is non-trivial.
- Graph $X$ is symmetric.
- Graph $X$ is locally similar, that means by looking at the vertices we can actually observe that locally they are same.
For example, Cayley Graph $X=(G,C)$ where $G$ is any group and $C$ is any subset of G which doesn't contain the identity and it's closed under inverse. Cayley graphs are regular and by construction, we can find a subgroup which is acting transitively on $X$.
Another important example is $J(5,2,0)$ Petersen graph. Here $S_5$ acts transitively on the vertex set{ which is nothing but the set of subsets of ${1,2,3,4,5}$ of size 2. }.
answered Nov 26 '16 at 3:38
Ashwin KoodathilAshwin Koodathil
667
667
add a comment |
add a comment |
$begingroup$
Its very similar to what homogeneity means in topological spaces.
Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.
$endgroup$
add a comment |
$begingroup$
Its very similar to what homogeneity means in topological spaces.
Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.
$endgroup$
add a comment |
$begingroup$
Its very similar to what homogeneity means in topological spaces.
Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.
$endgroup$
Its very similar to what homogeneity means in topological spaces.
Basically it means that if I am sitting in one of the vertices and I want to tell Steve which vertex I am at while on the phone, I am gonna be totally screwed, because the graph looks the same from every vertex.
edited Jan 26 at 22:39
answered Nov 26 '16 at 3:42


Jorge Fernández HidalgoJorge Fernández Hidalgo
76.8k1394195
76.8k1394195
add a comment |
add a comment |
$begingroup$
Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.
Graphs can be used to show group structure, for example:
This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.
Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.
Moving the identity element e
on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab
is still e
, it's all still the same object.
$endgroup$
add a comment |
$begingroup$
Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.
Graphs can be used to show group structure, for example:
This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.
Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.
Moving the identity element e
on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab
is still e
, it's all still the same object.
$endgroup$
add a comment |
$begingroup$
Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.
Graphs can be used to show group structure, for example:
This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.
Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.
Moving the identity element e
on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab
is still e
, it's all still the same object.
$endgroup$
Vertex transitive graphs are completely symmetric in the same way as the surface of a sphere is, every node has all the same properties as every other.
Graphs can be used to show group structure, for example:
This shows a dihedral symmetry group. It is the direct/cartesian multiplication of two simpler (sub) groups.
Note that (as a graph) it is also the direct multiplication of two vertex transitive graphs, and so it is also vertex transitive.
Moving the identity element e
on the above diagram and relabelling the rest of the graph doesn't change any of the resulting group structure, any of the groups properties/uses, abab
is still e
, it's all still the same object.
edited Jan 27 at 10:25
answered Jan 26 at 18:30
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%2f2030701%2fwhat-does-vertex-transitivity-tell-us-about-an-arbitrary-graph%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
3
$begingroup$
It means there is a pleasant symmetry to the graph. Consider the graph of a soccer ball, for example, where every vertex belongs to two hexagonal faces and a pentagonal face, and the vertices are interchangeable by spinning the ball.
$endgroup$
– Théophile
Nov 25 '16 at 21:11
$begingroup$
So back to our formal definition, what you said means that for each two vertices, I could find an automorphism,namely, a rotation from one vertex exactly toward the other? @Théophile
$endgroup$
– Ashkan Ranjbar
Nov 25 '16 at 22:10
$begingroup$
Yes, that's right. So it formalizes the idea of "you can't tell the difference between the vertices". An $n$-cycle is also vertex transitive: pick any $u,v in V$, and there is an obvious automorphism sending $u$ to $v$. To put it another way, there are no "special" vertices. A star, for example, where one central vertex $w$ is connected to a number of leaves, is not vertex transitive; you can easily distinguish $w$ from the leaves (which is an informal way of saying that no automorphism sends $w$ to a leaf).
$endgroup$
– Théophile
Nov 26 '16 at 2:06
$begingroup$
Compare also to edge transitivity, which is similar but (of course) applies to edges instead of vertices. A soccer ball is not edge transitive because there are two kinds of edges: either both endpoints are on the same pentagon, or they are on different pentagons. An $n$-cycle, on the other hand, is edge transitive.
$endgroup$
– Théophile
Nov 26 '16 at 2:09