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?

enter image description here

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.