# Non-isomorphic groups with the same oriented Cayley graph

There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following

$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets that generate the group ($\textit{i.e.}$ such that the words in $S \cup S^{-1}$ give the full group). Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are isomorphic, given that $S$ and $T$ are "mag".

PS: Here by Cayley graph of $G$ w.r.t. $S$, I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.

PPS: given minimality of $S$ and finiteness of the group, $S$ will usually be anti-symetric.

Here are examples. Take $G = \mathbb{Z}$ and $H= (\mathbb{Z}/2 \mathbb{Z}) *(\mathbb{Z}/2 \mathbb{Z})$. For $H$, picking $\lbrace a,b \rbrace$ the resulting Cayley graph is going to be infinite unoriented path ("two-way" infinite street). For $G$, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. In either case, the resulting (oriented) Cayley graph is going to be a infinite unorientd path ("one-way" infinite street).

There might be two questions: for finite groups and infinite groups. I suspect one could find them more easily by looking at infinite groups.

-
Two distinct 2-transitive groups of the same degree will suffice, as both Cayley graphs will be complete graphs. I assume you'd like more interesting examples, though. –  Brendan McKay Feb 23 '12 at 23:27
I think I just don't understand your statement. If the resulting graph is complete and $S$ is minimal as said above, then (unless I am mistaken, and this might very well be the case) it means every element is needed to generate the group and also that the product of two (non-trivial) elements should be the identity (otherwise it would mean this element would be generated by others. This forces the group to be $\mathbb{Z}/ 2\mathbb{Z}$... –  Antoine Feb 24 '12 at 17:18
Sorry, please discard my comment. –  Brendan McKay Feb 25 '12 at 7:41
Thanks for this comment. If the groups are finite (or is infinite, but generated by elements of finite order), then this assumption is indeed superfluous. I edited the post in order to clarify this point... I forgot to specify that I could not even find a counter-example when the groups are infinite. –  Antoine Feb 26 '12 at 10:44
You talk about the Cayley graphs of $G$ with respect to $S$ and $H$ with respect to $T$ being "identical", but since they are on different vertex sets, they cannot be actually identical. I guess you mean isomorphic rather than identical. –  Joel David Hamkins Feb 26 '12 at 14:55

If we consider the dihedral group of order 12, $G = \langle a, b \mid a^2 = b^2 = (ab)^6 = e \rangle$, then the Cayley graph corresponding to $\{ a, b \}$ is the cyclic graph on 12 vertices with edges labeled alternately by $a$ and $b$. We may then consider $H_1 = G \times \mathbb Z/2 \mathbb Z$ and $H_2 = G \rtimes \mathbb Z/2 \mathbb Z$ where the copies of $\mathbb Z/ 2 \mathbb Z$ are generated by $c$ and $d$ respectively, and where $d$ acts by $d a d = b$, $d b d = a$. Then the Cayley graph of $H_1$ with respect to $\{ a, b, c \}$ consists of two copies of cyclic graphs of order 12 with edges labeled by $c$ connecting the two graphs. Since $d$ just interchanges $a$ and $b$ we have that the Cayley graph of $H_2$ with respect to $\{ a, b, d \}$ can be obtained from the Cayley graph of $H_1$ by just relabeling the second copy of the cyclic graph, so that the two Cayley graphs will be isomorphic.

Unfortunately, the generating set for $H_2$ is not minimal since by the definition of $d$ we have $b \in \langle a, d \rangle$. This can be fixed however by taking two automorphisms $c$ and $d$ which are complicated enough so that this doesn't occur.

Specifically, we can let $c$ act on $G$ by $cac = ababa$, and $cbc = babab$, and we can let $d$ act on $G$ by applying $c$ and then interchanging $a$ and $b$, i.e., $dad = babab$, and $dbd = ababa$. It's not hard to see that these indeed define order two automorphisms of $G$, and for the same reason as above we have that the Cayley graphs of $H_1$ and $H_2$ will be isomorphic.

It is also not hard to check that we now have $| \langle a, c \rangle | = | \langle b, c \rangle | = 12 < 24$ and $| \langle a, d \rangle | = | \langle a, d \rangle | = 8 < 24$ so that the generating sets are now minimal. Moreover, the groups $H_1$ and $H_2$ will not be isomorphic, this can be seen for instance by counting the number of elements of order 2, (I counted 15 for $H_1$ and 9 for $H_2$, but I've omitted the tedious details).

-

Here are a couple of papers I found by googling "nonisomorphic groups with same Cayley digraph":

Morris, J. (1999), Isomorphic Cayley graphs on nonisomorphic groups. Journal of Graph Theory, 31: 345–362. (Available here: http://www.cs.uleth.ca/~morris/Research/AnneExtension.pdf)

and

Kovács, I. and Servatius, M. (2011), On Cayley digraphs on nonisomorphic 2-groups. Journal of Graph Theory. doi: 10.1002/jgt.20625,

which apparently extends Morris's results.

I haven't looked at these in enough detail to see whether they will answer your question, but it looks like Morris's paper would be a good place to start.

-
Clara Loeh has recently submitted a paper on arxiv for the case of finitely generated Abelian groups. I have not looked at the paper, but suspect it is for undirected graphs. Gerhard "Ask Me About System Design" Paseman, 2012.02.27 –  Gerhard Paseman Feb 27 '12 at 8:54
Yes, it is for undirected graphs. –  Tara Brough Feb 27 '12 at 9:57
Thanks for the further comments (question corrected) and apologies as I did not have time to look at the papers... My intuition was somehow against Abelian groups being potential counter-examples, but I could easily be wrong. –  Antoine Mar 1 '12 at 18:55