Definition: -Let $G$ be a group and $S$ a symmetric subset of $G$ (i.e. $s \in S$ if and only if $s^{ −1} \in S$), the Cayley graph $Cay(G; S)$ of $G$ w.r.t. $S$ is the graph whose vertex set is $G$ and $a \in G$ is connected to $\{sa| s \in S\}$. The Cayley graph $Cay(G; S)$ is $|S|$-regular graph.

-A graph $G$ is vertex-transitive if for any two vertices $x$ and $y$ of $G$ there is an automorphism of $G$ that sends $v$ to $v'$. Similarly, $G$ is edge-transitive if for any two edges $e$ and $e'$ of $G$ there is an automorphism of $G$ that sends $e$ to $e'$.

Background: It is well known that every Cayley graph is vertex transitive, but it is not always edge-transitive.

Question: Let $Cay(G,S)$ be a Cayley graph such that $o(s)=2$ for all $s\in S$ ($o(s)$ is the order of $s$). Must $Cay(G,S)$ be an edge-transitive graph ?

I'm pretty sure that this question has a positive answer, but I do not know how to prove it.

Any idea will be useful!


No. First take the group $S_3$, generated by $(12)$ and $(23)$. Both generators have order $2$, and the Cayley graph is a hexagon (so not a counterexample yet).

Now consider the product $S_3\times C_2$, with $S$ being those two generators together with the generator of $C_2$. In this case all three generators have order $2$, but the Cayley graph is a hexagonal prism, which is not edge-transitive.


Another counterexample is the Cayley graph of the octahedral group, i.e. the Coxeter group with presentation $$ \langle a, b, c \mid a^2 = b^2 = c^2 = (ab)^3 = (ac)^2 = (bc)^4 = 1 \rangle. $$ The edges corresponding to generators $a$ and $b$ lie on hexagonal cycles, but the edges of type $c$ do not.


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.