2
$\begingroup$

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!

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Why isn't Cayley graph of $S_3 \times C_2$ edge-transitive? $\endgroup$
    – M.Ramana
    May 26, 2021 at 17:06
  • $\begingroup$ @M.Ramana one way to see it is to look at the number of squares containing a given edge. This is $2$ for some edges and $1$ for others. $\endgroup$ May 26, 2021 at 18:30
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .