Non-isomorphic groups with the same oriented Cayley graph

Question

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

Apologies in advance if the answer is well-known...

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.

Answer 1

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

Answer 2

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.