Can we get the line graph of the $3D$ cube as a Cayley graph?

204 Views Asked by At

Given a graph $G=(V,E)$, the line graph of $G$ is a graph $\Gamma$ whose vertices are $E$ (the edges of $G$) and in $\Gamma$, two vertices $e_1,e_2$ are connected if, as edges in $G$, they share an endpoint.

Now let $G$ be the $3D$ cube graph. It has $8$ vertices, $12$ edges and it is $3$-regular. It is actually the Cayley graph of $\mathbb{Z}_2^3$ with generators $(1,0,0),(0,1,0),(0,0,1)$.

Let $\Gamma$ be the line graph of this $G$. Then $\Gamma$ has $12$ vertices and it is $4$-regular and highly symmetric.

Is $\Gamma$ the Cayley graph of some group $H$ (of order $12$) with a symmetric set of generator $S \subset H$ ($|S|=4$)?

(by a symmetric set I mean that $x\in S \Rightarrow x^{-1}\in S$, making the Cayley graph undirected).

2

There are 2 best solutions below

3
On BEST ANSWER

I haven't checked this, but try $H=A_4$, with $S=\{g,h,g^{-1},h^{-1}\}$ where $g=(1,2,3)$ and $h=(2,3,4)$. So vertices of the cube are labelled alternately with $g$ and $h$, and multiplication of an element (egde) by a generator (vertex) corresponds to rotating the edge clockwise round that vertex (or anticlockwise for multiplication by the inverse).

0
On

C.Hagemeyer & R.Scott, On Groups with Cayley Graph Isomorphic to a Cube. Communications in Algebra, v.42, No.4, 2014, pp.1484-1495.