What is a vertex-transitive graph? (Question about Lovász Conjecture)Finite Vertex-Transitive Planar game of...
How do I locate a classical quotation?
What Happens when Passenger Refuses to Fly Boeing 737 Max?
"One can do his homework in the library"
Examples of a statistic that is not independent of sample's distribution?
Accountant/ lawyer will not return my call
Does splitting a potentially monolithic application into several smaller ones help prevent bugs?
Why would one plane in this picture not have gear down yet?
Is it true that real estate prices mainly go up?
Is "history" a male-biased word ("his+story")?
Good for you! in Russian
Peter's Strange Word
Algorithm to convert a fixed-length string to the smallest possible collision-free representation?
What is the likely impact of grounding an entire aircraft series?
Unreachable code, but reachable with exception
Is there an equal sign with wider gap?
Force user to remove USB token
If the Captain's screens are out, does he switch seats with the co-pilot?
Can someone explain what is being said here in color publishing in the American Mathematical Monthly?
Am I not good enough for you?
Why is Beresheet doing a only a one-way trip?
How are such low op-amp input currents possible?
Why don't MCU characters ever seem to have language issues?
Solving "Resistance between two nodes on a grid" problem in Mathematica
In the late 1940’s to early 1950’s what technology was available that could melt a LOT of ice?
What is a vertex-transitive graph? (Question about Lovász Conjecture)
Finite Vertex-Transitive Planar game of Civilization?What's the difference between the automorphism and isomorphism of graph?Proving every planar graph have vertex cover of size of at most 3n/4What is Graph Isomorphism and Graph Invariant?On 6-regular vertex-transitive graphs having 42 nodesIs this Cayley graph edge-transitive?Is the Erdős–Faber–Lovász conjecture open still?Hamiltonian Path on Cubic Graphs, and whether closed triangle meshes are triangle stripsClosure of an Undirected GraphA question related to the binding number of a graph
$begingroup$
I was reading about Lovász Conjecture and came across the following definition on Wikipedia of a vertex-transitive graph (see below).
$bullet$ It states that a graph is vertex-transitive if for any two vertices $u$ and $v$ of the graph, there is some automorphism (i.e. a relabeling of vertices of a graph) $f: V(G)rightarrow V(G)$ where $f(u)=v$.
$textbf{QUESTION:}$ I'm having a hard time figuring out how to use this definition in this context; so, my question is why are certain graphs vertex transitive and others not? For example, what is the function for the graph below that makes it vertex transitive?
graph-theory hamiltonian-path
asked Mar 9 at 16:50
W. G.W. G.
6991718
$endgroup$
add a comment |
$begingroup$
I was reading about Lovász Conjecture and came across the following definition on Wikipedia of a vertex-transitive graph (see below).
$bullet$ It states that a graph is vertex-transitive if for any two vertices $u$ and $v$ of the graph, there is some automorphism (i.e. a relabeling of vertices of a graph) $f: V(G)rightarrow V(G)$ where $f(u)=v$.
$textbf{QUESTION:}$ I'm having a hard time figuring out how to use this definition in this context; so, my question is why are certain graphs vertex transitive and others not? For example, what is the function for the graph below that makes it vertex transitive?
graph-theory hamiltonian-path
asked Mar 9 at 16:50
W. G.W. G.
6991718
$endgroup$
2
$begingroup$
It's not a single function which makes the graph vertex transitive. In the graph you drew, for example, you have an automorphism which swaps $v_1,v_4$ and fixes the other two graphs, and so on.
$endgroup$
– Wojowu
Mar 9 at 16:57
add a comment |
$begingroup$
I was reading about Lovász Conjecture and came across the following definition on Wikipedia of a vertex-transitive graph (see below).
$bullet$ It states that a graph is vertex-transitive if for any two vertices $u$ and $v$ of the graph, there is some automorphism (i.e. a relabeling of vertices of a graph) $f: V(G)rightarrow V(G)$ where $f(u)=v$.
$textbf{QUESTION:}$ I'm having a hard time figuring out how to use this definition in this context; so, my question is why are certain graphs vertex transitive and others not? For example, what is the function for the graph below that makes it vertex transitive?
graph-theory hamiltonian-path
asked Mar 9 at 16:50
W. G.W. G.
6991718
$endgroup$
I was reading about Lovász Conjecture and came across the following definition on Wikipedia of a vertex-transitive graph (see below).
$bullet$ It states that a graph is vertex-transitive if for any two vertices $u$ and $v$ of the graph, there is some automorphism (i.e. a relabeling of vertices of a graph) $f: V(G)rightarrow V(G)$ where $f(u)=v$.
$textbf{QUESTION:}$ I'm having a hard time figuring out how to use this definition in this context; so, my question is why are certain graphs vertex transitive and others not? For example, what is the function for the graph below that makes it vertex transitive?
graph-theory hamiltonian-path
graph-theory hamiltonian-path
asked Mar 9 at 16:50
W. G.W. G.
6991718
asked Mar 9 at 16:50
W. G.W. G.
6991718
asked Mar 9 at 16:50
W. G.W. G.
6991718
asked Mar 9 at 16:50
W. G.W. G.
6991718
asked Mar 9 at 16:50
W. G.W. G.
6991718
6991718
2
$begingroup$
It's not a single function which makes the graph vertex transitive. In the graph you drew, for example, you have an automorphism which swaps $v_1,v_4$ and fixes the other two graphs, and so on.
$endgroup$
– Wojowu
Mar 9 at 16:57
add a comment |
2
$begingroup$
It's not a single function which makes the graph vertex transitive. In the graph you drew, for example, you have an automorphism which swaps $v_1,v_4$ and fixes the other two graphs, and so on.
$endgroup$
– Wojowu
Mar 9 at 16:57
2
2
$begingroup$
It's not a single function which makes the graph vertex transitive. In the graph you drew, for example, you have an automorphism which swaps $v_1,v_4$ and fixes the other two graphs, and so on.
$endgroup$
– Wojowu
Mar 9 at 16:57
$begingroup$
It's not a single function which makes the graph vertex transitive. In the graph you drew, for example, you have an automorphism which swaps $v_1,v_4$ and fixes the other two graphs, and so on.
$endgroup$
– Wojowu
Mar 9 at 16:57
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose you wanted to swap $v_1$ and $v_2$. Then, you could leave $v_3$ and $v_4$, and all of the connections in the graph would be the same (e.g. the new $v_1$ and the old $v_1$ are both still connected to the vertices labelled $v_2,v_3,v_4$). This graph is $K_4$ which is particularly nice in that any rearrangement preserves that property.
To see an example that wouldn't work, take a graph with two vertices of different degree. Then, no matter how you try to swap them you won't be able to get a graph with the same connectivity relationships.
answered Mar 9 at 16:57
Michael BiroMichael Biro
10.9k21831
$endgroup$
$begingroup$
That helps out a lot! Thank you! So, in the case of swapping $v_1$ and $v_2$; the function $f$ would be $f={ (v_1, v_2), (v_2, v_1), (v_3, v_3), (v_4, v_4)}$ which preserves the same edge vertex connectivity as before. So, my question is in the case of other graphs, do we have to necessarily keep $v_3$ mapping to $v_3$ and $v_4$ to $v_4$ after swapping $v_1$ and $v_2$ to see if we have the same vertex connectivity as before or could we swap some other vertices around too to see if we have the same edge vertex connectivity as before?
$endgroup$
– W. G.
Mar 9 at 17:40
$begingroup$
I think its the latter (where other vertices could be switched around), but I'm not quite sure..
$endgroup$
– W. G.
Mar 9 at 17:45
1
$begingroup$
No, not necessarily, it would depend on the graph. Any permutation of the vertices of $K_4$ gives a valid automorphism (which is a special property of complete graphs). So you could do $v_1 rightarrow v_2$, $v_2 rightarrow v_1$, $v_3 rightarrow v_4$ and $v_4 rightarrow v_3$.
$endgroup$
– Michael Biro
Mar 9 at 17:48
1
$begingroup$
Thank you!!! I got it now! I appreciate your time.
$endgroup$
– W. G.
Mar 9 at 17:48
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%2f3141329%2fwhat-is-a-vertex-transitive-graph-question-about-lov%25c3%25a1sz-conjecture%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose you wanted to swap $v_1$ and $v_2$. Then, you could leave $v_3$ and $v_4$, and all of the connections in the graph would be the same (e.g. the new $v_1$ and the old $v_1$ are both still connected to the vertices labelled $v_2,v_3,v_4$). This graph is $K_4$ which is particularly nice in that any rearrangement preserves that property.
To see an example that wouldn't work, take a graph with two vertices of different degree. Then, no matter how you try to swap them you won't be able to get a graph with the same connectivity relationships.
answered Mar 9 at 16:57
Michael BiroMichael Biro
10.9k21831
$endgroup$
$begingroup$
That helps out a lot! Thank you! So, in the case of swapping $v_1$ and $v_2$; the function $f$ would be $f={ (v_1, v_2), (v_2, v_1), (v_3, v_3), (v_4, v_4)}$ which preserves the same edge vertex connectivity as before. So, my question is in the case of other graphs, do we have to necessarily keep $v_3$ mapping to $v_3$ and $v_4$ to $v_4$ after swapping $v_1$ and $v_2$ to see if we have the same vertex connectivity as before or could we swap some other vertices around too to see if we have the same edge vertex connectivity as before?
$endgroup$
– W. G.
Mar 9 at 17:40
$begingroup$
I think its the latter (where other vertices could be switched around), but I'm not quite sure..
$endgroup$
– W. G.
Mar 9 at 17:45
1
$begingroup$
No, not necessarily, it would depend on the graph. Any permutation of the vertices of $K_4$ gives a valid automorphism (which is a special property of complete graphs). So you could do $v_1 rightarrow v_2$, $v_2 rightarrow v_1$, $v_3 rightarrow v_4$ and $v_4 rightarrow v_3$.
$endgroup$
– Michael Biro
Mar 9 at 17:48
1
$begingroup$
Thank you!!! I got it now! I appreciate your time.
$endgroup$
– W. G.
Mar 9 at 17:48
add a comment |
$begingroup$
Suppose you wanted to swap $v_1$ and $v_2$. Then, you could leave $v_3$ and $v_4$, and all of the connections in the graph would be the same (e.g. the new $v_1$ and the old $v_1$ are both still connected to the vertices labelled $v_2,v_3,v_4$). This graph is $K_4$ which is particularly nice in that any rearrangement preserves that property.
To see an example that wouldn't work, take a graph with two vertices of different degree. Then, no matter how you try to swap them you won't be able to get a graph with the same connectivity relationships.
answered Mar 9 at 16:57
Michael BiroMichael Biro
10.9k21831
$endgroup$
$begingroup$
That helps out a lot! Thank you! So, in the case of swapping $v_1$ and $v_2$; the function $f$ would be $f={ (v_1, v_2), (v_2, v_1), (v_3, v_3), (v_4, v_4)}$ which preserves the same edge vertex connectivity as before. So, my question is in the case of other graphs, do we have to necessarily keep $v_3$ mapping to $v_3$ and $v_4$ to $v_4$ after swapping $v_1$ and $v_2$ to see if we have the same vertex connectivity as before or could we swap some other vertices around too to see if we have the same edge vertex connectivity as before?
$endgroup$
– W. G.
Mar 9 at 17:40
$begingroup$
I think its the latter (where other vertices could be switched around), but I'm not quite sure..
$endgroup$
– W. G.
Mar 9 at 17:45
1
$begingroup$
No, not necessarily, it would depend on the graph. Any permutation of the vertices of $K_4$ gives a valid automorphism (which is a special property of complete graphs). So you could do $v_1 rightarrow v_2$, $v_2 rightarrow v_1$, $v_3 rightarrow v_4$ and $v_4 rightarrow v_3$.
$endgroup$
– Michael Biro
Mar 9 at 17:48
1
$begingroup$
Thank you!!! I got it now! I appreciate your time.
$endgroup$
– W. G.
Mar 9 at 17:48
add a comment |
$begingroup$
Suppose you wanted to swap $v_1$ and $v_2$. Then, you could leave $v_3$ and $v_4$, and all of the connections in the graph would be the same (e.g. the new $v_1$ and the old $v_1$ are both still connected to the vertices labelled $v_2,v_3,v_4$). This graph is $K_4$ which is particularly nice in that any rearrangement preserves that property.
To see an example that wouldn't work, take a graph with two vertices of different degree. Then, no matter how you try to swap them you won't be able to get a graph with the same connectivity relationships.
answered Mar 9 at 16:57
Michael BiroMichael Biro
10.9k21831
$endgroup$
Suppose you wanted to swap $v_1$ and $v_2$. Then, you could leave $v_3$ and $v_4$, and all of the connections in the graph would be the same (e.g. the new $v_1$ and the old $v_1$ are both still connected to the vertices labelled $v_2,v_3,v_4$). This graph is $K_4$ which is particularly nice in that any rearrangement preserves that property.
To see an example that wouldn't work, take a graph with two vertices of different degree. Then, no matter how you try to swap them you won't be able to get a graph with the same connectivity relationships.
answered Mar 9 at 16:57
Michael BiroMichael Biro
10.9k21831
answered Mar 9 at 16:57
Michael BiroMichael Biro
10.9k21831
answered Mar 9 at 16:57
Michael BiroMichael Biro
10.9k21831
answered Mar 9 at 16:57
Michael BiroMichael Biro
10.9k21831
10.9k21831
$begingroup$
That helps out a lot! Thank you! So, in the case of swapping $v_1$ and $v_2$; the function $f$ would be $f={ (v_1, v_2), (v_2, v_1), (v_3, v_3), (v_4, v_4)}$ which preserves the same edge vertex connectivity as before. So, my question is in the case of other graphs, do we have to necessarily keep $v_3$ mapping to $v_3$ and $v_4$ to $v_4$ after swapping $v_1$ and $v_2$ to see if we have the same vertex connectivity as before or could we swap some other vertices around too to see if we have the same edge vertex connectivity as before?
$endgroup$
– W. G.
Mar 9 at 17:40
$begingroup$
I think its the latter (where other vertices could be switched around), but I'm not quite sure..
$endgroup$
– W. G.
Mar 9 at 17:45
1
$begingroup$
No, not necessarily, it would depend on the graph. Any permutation of the vertices of $K_4$ gives a valid automorphism (which is a special property of complete graphs). So you could do $v_1 rightarrow v_2$, $v_2 rightarrow v_1$, $v_3 rightarrow v_4$ and $v_4 rightarrow v_3$.
$endgroup$
– Michael Biro
Mar 9 at 17:48
1
$begingroup$
Thank you!!! I got it now! I appreciate your time.
$endgroup$
– W. G.
Mar 9 at 17:48
add a comment |
$begingroup$
That helps out a lot! Thank you! So, in the case of swapping $v_1$ and $v_2$; the function $f$ would be $f={ (v_1, v_2), (v_2, v_1), (v_3, v_3), (v_4, v_4)}$ which preserves the same edge vertex connectivity as before. So, my question is in the case of other graphs, do we have to necessarily keep $v_3$ mapping to $v_3$ and $v_4$ to $v_4$ after swapping $v_1$ and $v_2$ to see if we have the same vertex connectivity as before or could we swap some other vertices around too to see if we have the same edge vertex connectivity as before?
$endgroup$
– W. G.
Mar 9 at 17:40
$begingroup$
I think its the latter (where other vertices could be switched around), but I'm not quite sure..
$endgroup$
– W. G.
Mar 9 at 17:45
1
$begingroup$
No, not necessarily, it would depend on the graph. Any permutation of the vertices of $K_4$ gives a valid automorphism (which is a special property of complete graphs). So you could do $v_1 rightarrow v_2$, $v_2 rightarrow v_1$, $v_3 rightarrow v_4$ and $v_4 rightarrow v_3$.
$endgroup$
– Michael Biro
Mar 9 at 17:48
1
$begingroup$
Thank you!!! I got it now! I appreciate your time.
$endgroup$
– W. G.
Mar 9 at 17:48
$begingroup$
That helps out a lot! Thank you! So, in the case of swapping $v_1$ and $v_2$; the function $f$ would be $f={ (v_1, v_2), (v_2, v_1), (v_3, v_3), (v_4, v_4)}$ which preserves the same edge vertex connectivity as before. So, my question is in the case of other graphs, do we have to necessarily keep $v_3$ mapping to $v_3$ and $v_4$ to $v_4$ after swapping $v_1$ and $v_2$ to see if we have the same vertex connectivity as before or could we swap some other vertices around too to see if we have the same edge vertex connectivity as before?
$endgroup$
– W. G.
Mar 9 at 17:40
$begingroup$
That helps out a lot! Thank you! So, in the case of swapping $v_1$ and $v_2$; the function $f$ would be $f={ (v_1, v_2), (v_2, v_1), (v_3, v_3), (v_4, v_4)}$ which preserves the same edge vertex connectivity as before. So, my question is in the case of other graphs, do we have to necessarily keep $v_3$ mapping to $v_3$ and $v_4$ to $v_4$ after swapping $v_1$ and $v_2$ to see if we have the same vertex connectivity as before or could we swap some other vertices around too to see if we have the same edge vertex connectivity as before?
$endgroup$
– W. G.
Mar 9 at 17:40
$begingroup$
I think its the latter (where other vertices could be switched around), but I'm not quite sure..
$endgroup$
– W. G.
Mar 9 at 17:45
$begingroup$
I think its the latter (where other vertices could be switched around), but I'm not quite sure..
$endgroup$
– W. G.
Mar 9 at 17:45
1
1
$begingroup$
No, not necessarily, it would depend on the graph. Any permutation of the vertices of $K_4$ gives a valid automorphism (which is a special property of complete graphs). So you could do $v_1 rightarrow v_2$, $v_2 rightarrow v_1$, $v_3 rightarrow v_4$ and $v_4 rightarrow v_3$.
$endgroup$
– Michael Biro
Mar 9 at 17:48
$begingroup$
No, not necessarily, it would depend on the graph. Any permutation of the vertices of $K_4$ gives a valid automorphism (which is a special property of complete graphs). So you could do $v_1 rightarrow v_2$, $v_2 rightarrow v_1$, $v_3 rightarrow v_4$ and $v_4 rightarrow v_3$.
$endgroup$
– Michael Biro
Mar 9 at 17:48
1
1
$begingroup$
Thank you!!! I got it now! I appreciate your time.
$endgroup$
– W. G.
Mar 9 at 17:48
$begingroup$
Thank you!!! I got it now! I appreciate your time.
$endgroup$
– W. G.
Mar 9 at 17:48
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%2f3141329%2fwhat-is-a-vertex-transitive-graph-question-about-lov%25c3%25a1sz-conjecture%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
2
$begingroup$
It's not a single function which makes the graph vertex transitive. In the graph you drew, for example, you have an automorphism which swaps $v_1,v_4$ and fixes the other two graphs, and so on.
$endgroup$
– Wojowu
Mar 9 at 16:57