Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I suspect that the answer to my question is well-known to be no. To be more precise, let $G$ and $H$ be nonisomorphic finite groups of the same order. Let $S \subseteq G$ and $T \subseteq H$ be subsets satisfying the three properties: (1) the subsets are symmetric, that is $S = S^{-1}$ and $T = T^{-1}$; (2) they are minimal symmetric generating sets; (3) the size of $S$ is equal to the size of $T$. Is it possible for the Cayley graph of the pair $(G,S)$ and the Cayley graph of the pair $(H,T)$ to be isomorphic?

If the answer is yes, what is the smallest such example?

share|improve this question

2 Answers 2

up vote 15 down vote accepted

The truncated cube (polyhedron with eight triangular faces and six octagonal faces) is a Cayley graph of both the symmetric group on four items (generators: transpose first two of the four items, rotate the last three) and of a different group that acts on 3-bit binary strings (generators: rotate the string, flip its first bit). You can tell they're different Cayley graphs because the graph isomorphism does not preserve the Cayley labeling: in one of the two Cayley graphs, the generators labeling the triangles are inverted on half of the triangles compared to the labeling of the other graph. See this blog post.

share|improve this answer
    
That's great -- thanks a lot! –  cfranc Feb 8 '10 at 21:20
    
+1. This answer is an answer to part of a question at mathoverflow.net/questions/14830/which-graphs-are-cayley-graphs. –  Joel David Hamkins Feb 10 '10 at 3:50

Let $G = Z_4$ be the cyclic group on 4 elements, generated by $S = \{-1,1 \}$, let $H = Z_2 \times Z_2$ be the Klein four group, generated by $T = \{(0,1),(1,0)\}$. Then $|S| = |T|$ and both Cayley graphs are isomorphic to $C_4$, the cycle of length 4.

For $n > 2$ each even cycle $C_{2n}$ is a Cayley graph for the cyclic group $Z_{2n}$ and for the dihedral group $D_n$ of order $2n$.

Another well-known example is the graph of a cube $Q_3$ which is a Cayley graph for the abelian group $Z_4 \times Z_2$ and for the dihedral group $D_4$. In the previous example the dihedral group was generated by two involutions, while in the latter case it is generated by an involution and an element of order 4.

If only generators are counted, without their inverses, the first two examples do not give matching counts.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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