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

  • 1
    $\begingroup$ There are only 5 groups of order 12 (up to isomorphism). Have you tried any of them on for size? $\endgroup$ – Gerry Myerson Jun 12 '13 at 9:47
  • $\begingroup$ @Gerry: I looked in wikipedia, but it is not just a matter of choosing the group, but also choosing the generators. So, although I didn't see how to do it, I might have chosen the generators in the wrong way. $\endgroup$ – Alex Jun 12 '13 at 10:08
  • $\begingroup$ @user1729: I think I need to choose $4$ generators of of group of size $12$, because every edge is adjacent to 4 other. $\endgroup$ – Alex Jun 12 '13 at 10:20
  • $\begingroup$ @Alex Sorry, I meant four, and then I realised that it should be $4/2=2$, or there are generators of order two... $\endgroup$ – user1729 Jun 12 '13 at 10:21
  • $\begingroup$ OK, but maybe you can rule out some of the groups. $\endgroup$ – Gerry Myerson Jun 12 '13 at 10:35

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

  • $\begingroup$ Do you mean $H=A_4$? $\endgroup$ – Alex Jun 12 '13 at 10:16
  • $\begingroup$ Indeed I do. Will edit. $\endgroup$ – aPaulT Jun 12 '13 at 10:27
  • 1
    $\begingroup$ I have references to support this: I think my line graph is this which can be found as this Cayley Graph here $\endgroup$ – Alex Jun 12 '13 at 11:39

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


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.