Dtjytyk

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

1

$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

share|cite|improve this question

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 | 

1

$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

share|cite|improve this question

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

share|cite|improve this question

asked Mar 9 at 16:50

W. G.W. G.

6991718

$endgroup$

share|cite|improve this question

asked Mar 9 at 16:50

W. G.W. G.

6991718

share|cite|improve this question

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

1 Answer
1

active

oldest

votes

1

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

share|cite|improve this answer

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
});


}
});

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

1

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

share|cite|improve this answer

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 | 

1

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

share|cite|improve this answer

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.

share|cite|improve this answer

answered Mar 9 at 16:57

Michael BiroMichael Biro

10.9k21831

$endgroup$

share|cite|improve this answer

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