ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.867644 J. Algebra Comb. Discrete Appl. 8(1) • 53–57 Received: 24 May 2020 Accepted: 19 October 2020 Journal of Algebra Combinatorics Discrete Structures and Applications Two families of graphs that are Cayley on nonisomorphic groups∗ Research Article Joy Morris, Josip Smolčić Abstract: A number of authors have studied the question of when a graph can be represented as a Cayley graph on more than one nonisomorphic group. The work to date has focussed on a few special situations: when the groups are p-groups; when the groups have order pq; when the Cayley graphs are normal; or when the groups are both abelian. In this paper, we construct two infinite families of graphs, each of which is Cayley on an abelian group and a nonabelian group. These families include the smallest examples of such graphs that had not appeared in other results. 2010 MSC: 05C25, 05C60 Keywords: Cayley graphs, Nonisomorphic groups 1. Introduction A Cayley graph Cay(G,S) on a group G with connection set S, is the graph whose vertices are the elements of G, with two vertices g1 and g2 adjacent if and only if g2 = sg1 for some s ∈ S. In order to ensure that this is a graph rather than a directed graph, we must require that S = S−1; that is, S is closed under inversion; if we omit this condition, we obtain digraphs (and an arc from g1 to g2 rather than an edge between them). Conventionally we also generally assume that the identity e of G is not in S; this avoids having loops at every vertex. Cayley graphs and digraphs are a major area of study, as their symmetries lead to many useful properties in the networks they represent. We use standard notation for graphs. In particular, in a graph Γ, V (Γ) represents its vertex set, while we use v ∼ u to indicate that there is an edge between the vertices v and u. It is well known (first observed by Sabidussi) that a (di)graph can be represented as a Cayley (di)graph on the group G if and only if its automorphism group contains a subgroup isomorphic to G ∗ This work was supported by the Natural Science and Engineering Research Council of Canada (grant RGPIN- 2017-04905). Josip Smolčić worked on this project as a summer research experience supported out of this grant. Joy Morris (Corresponding Author), Josip Smolčić; Department of Mathematics and Computer Science, Uni- versity of Lethbridge, Lethbridge, Canada (email: joy.morris@uleth.ca, josip.smolcic@uleth.ca). 53 https://orcid.org/0000-0003-2416-669X https://orcid.org/0000-0002-7456-3100 J. Morris, J. Smolčić / J. Algebra Comb. Discrete Appl. 8(1) (2021) 53–57 in its regular action. However, a particular representation of a Cayley (di)graph may not be its only representation, either on a fixed group, or on different groups. Sometimes a particular representation may be more useful for practical purposes than a different representation, so it is of interest to understand all possible representations. In this paper, we construct two infinite families of graphs, each of which is Cayley on an abelian group and a nonabelian group. These families include the smallest examples of such graphs that had not appeared in other results. The so-called "Cayley Isomorphism" (CI) problem studies whether or not all representations for a given Cayley graph on some fixed group G can be determined purely algebraically. It is therefore a large part of the question of when a Cayley graph on a group G is isomorphic to another Cayley graph on the same group G (or, equivalently, when there are two distinct regular subgroups isomorphic to G in the automorphism group of the graph). The CI problem has been extensively studied by many researchers. For example, the papers [1–3, 10, 15, 16] amongst many others, and the survey article [9] all deal with this question. The question of when a Cayley graph on G can be represented as a Cayley graph on some noniso- morphic group H has also received some attention. Joseph in 1995 [7] determined necessary and sufficient conditions for a Cayley digraph of order p2 (where p is prime), to be isomorphic to a Cayley digraph of both groups of order p2 ([6, Lemma 4] provides a group theoretic version of this result). The first author [13, 14] subsequently extended this result and determined necessary and sufficient conditions for a Cayley digraph of the cyclic group of order pk, k ≥ 1 and p an odd prime, to be isomorphic to a Cayley digraph of some other group of order pk. The equivalent problem for p = 2 (when both groups are abelian) was solved by Kovács and Servatius [8]. In these cases, graphs that could be represented on both groups are all "wreath" (or "lexicographic") products, and their automorphism groups are significantly larger than the number of vertices. In contrast, when neither group is cyclic, [12] shows that it is often possible to find Cayley digraphs that can be represented on two nonisomorphic p-groups (one abelian and the other not) whose automorphism group is only slightly larger than the original groups. Recent work by Dobson and the first author [5] considers graphs that are Cayley on more than one abelian group when the number of vertices is not a prime power. Digraphs of order pq that are Cayley graphs of both groups of order pq, where q | (p− 1) and p,q are distinct primes were determined by Dobson in [4, Theorem 3.4]. Marušič and the first author studied the question of which normal circulant graphs of square-free order are also Cayley graphs of a nonabelian group [11]. Some of the graphs in our families fall into each of these categories, but neither of our families is limited to square-free orders. 2. The families The first of these families may be known to researchers, but to the best of our knowledge no proof has previously appeared in the literature. A circulant graph is a Cayley graph on a cyclic group, and we use Dk to denote the dihedral group of order 2k. Proposition 2.1. Let Γ be a circulant graph on n = 2k vertices. Then Γ is a Cayley graph on Dk and Cn. Proof. Let Γ = Cay(Cn,S), where S ⊂ Cn is closed under inverses, and Cn = 〈c〉. By assumption, Γ is a Cayley graph on Cn. We must show that Γ is also a Cayley graph on Dk. We do this by finding a regular subgroup of Aut(Γ) that is isomorphic to Dk. Define α and β by α(z) = zc2 and β(z) = z−1c−1 for z ∈ V (Γ) = Cn. We first show that α and β are automorphisms. For every u,v ∈ V (Γ) with u ∼ v, there exists s ∈ S 54 J. Morris, J. Smolčić / J. Algebra Comb. Discrete Appl. 8(1) (2021) 53–57 such that su = v. It is not hard to see that sα(u) = suc2 = vc2 = α(v). Also, since S is closed under inverses and u and s are both elements of the abelian group Cn, we have s−1β(u) = s−1u−1c−1 = (us)−1c−1 = v−1c−1 = β(v) as desired. Since n = 2k is the order of c, it is clear that α has order k. Also β2(z) = β(z−1c−1) = (z−1c−1)−1c−1 = czc−1 = z, thus β has order 2. Finally, β−1αβ(z) = βα(z−1c−1) = β(z−1c) = zc−2 = α−1(z), so β inverts α. We conclude that 〈α,β〉∼= Dk is a subgroup of Aut(Γ). It remains to observe that 〈α,β〉 acts regularly on the vertices of Γ. Since |〈α,β〉| = n, it is sufficient to show that 〈α,β〉 is acting transitively on the vertices of Γ. Let u = ci and v = cj be arbitrary vertices of Γ. If i and j have the same parity, then cj = ci+2m for some m ∈ Z, in which case it is easy to see that v = cj = αm(ci) = αm(u). On the other hand, if i and j have opposite parities, then β(u) = u−1c−1 = c−i−1 and −i− 1 has the same parity as j. Again this implies that there exists some integer m such that v = cj = αm(c−i−1) = αmβ(u). Thus the action of 〈α,β〉 is regular, and therefore Γ is a Cayley graph on Dk. The second family has slightly more restrictions, but is at the same time potentially more interesting. To understand it, we must define the family of generalised dihedral groups. Definition 2.2. Let A be an abelian group. Define the group Dih(A,x) = 〈A,x〉, where x2 = 1 and x−1ax = a−1 for every a ∈ A. Notice that Dih(A,x) ∼= A o C2 where C2 acts by inversion. In the special case where A is cyclic, this is the usual dihedral group. Notice that the group Dih(A,x) is abelian if and only if A is an elementary abelian 2-group, in which case Dih(A,x) is the elementary abelian 2-group whose rank is one higher than the rank of A. The following theorem shows that for a particular slightly restricted family of connection sets, Cayley graphs on the generalised dihedral group Dih(A,x) = A o C2 are also Cayley graphs on A×C2. Theorem 2.3. Let A be an abelian group, and let D = Dih(A,x) be the corresponding generalised dihedral group. Let S ⊆ D be closed under inversion, and let Γ = Cay(D,S). Suppose that there is some y ∈ xA such that for every a ∈ A we have ya ∈ S ∩ xA if and only if ya−1 ∈ S ∩xA. Then Aut(Γ) has a regular subgroup isomorphic to A×C2, so Γ is also a Cayley graph on the abelian group A×C2. Proof. First note that if A is an elementary abelian 2-group, then Dih(A,x) ∼= A × C2 so there is nothing to prove. For every a ∈ A, define the map αa on the vertices of Γ by αa(z) = za, and define the map β by β(z) = yz for all z ∈ V (Γ) = D. Let H = 〈αa,β : a ∈ A〉. We claim that H ∼= A × C2 is a regular subgroup of Aut(Γ). First we show that H ∼= A × C2. It should be clear that 〈αa : a ∈ A〉 ∼= A. Furthermore, since y ∈ xA we have y = xa for some a ∈ A, so y2 = xaxa = a−1a = 1, meaning that β has order 2. It remains only to show that H is abelian. Again, since A is abelian, we really only need to show that β commutes with every αa. This is easy, since βαa(z) = β(za) = yza = αa(yz) = αaβ(z). For the remainder of the proof, we must show that H consists of automorphisms of Γ. Let u,v ∈ V (Γ), where u ∼ v, so there is some s ∈ S such that v = su. It is easy to see that for any αa ∈ H, αa is an element of the right regular action of Dih(A,x) on Γ, and is therefore an automorphism of Γ. 55 J. Morris, J. Smolčić / J. Algebra Comb. Discrete Appl. 8(1) (2021) 53–57 To show that β is also an automorphism of Γ, we will require the extra conditions we assumed for S: that S is inverse-closed (which is necessary for Γ to be a graph rather than a digraph) and also that for every a ∈ A, we have ya ∈ S if and only if ya−1 ∈ S. We will also need the observation that for every a ∈ A, y−1ay = yay = a−1; this follows immediately from the definitions of y and x and the fact that A is abelian. Again, we take u,v ∈ V (Γ) where u ∼ v, so there is some s ∈ S such that v = su. We deal separately with the possibilities that s ∈ A or s ∈ xA = yA. Suppose first that s ∈ A, so that s−1y = ys. Since S is closed under inverses s−1β(u) = s−1yu = ysu = yv = β(v). Thus β(u) ∼ β(v) if and only if u ∼ v, meaning that β is an automorphism of Γ. Now suppose that s ∈ xA = yA, say s = yb where b ∈ A. Then yb−1 is also in S, and yb−1β(u) = yb−1yu = y(yb)u = ysu = yv = β(v). Thus β(u) ∼ β(v) if and only if u ∼ v, meaning that β is an automorphism of Γ. We have shown that H ≤ Aut(Γ). Since |H| = 2|A| = |D|, in order to show that H is a regular subgroup of Aut(Γ) we need only show that it is transitive. It should be apparent that 〈αa : a ∈ A〉≤ D,H is transitive on each coset of A in V (Γ), so we need only show that β interchanges the cosets. Let u ∈ V (Γ). If u = a ∈ A, then β(u) = ya ∈ xA since y ∈ xA. Likewise, if u = xa ∈ xA, then β(u) = yxa ∈ A. Thus, H is indeed a regular subgroup of Aut(Γ). In the case where A is not an elementary abelian 2-group, we have shown that such graphs are Cayley graphs on both the abelian group A×C2 and the nonabelian group Dih(A,x), which are nonisomorphic. It is easy to construct examples of graphs that satisfy our restriction on the connection set; for example, any connection set that contains exactly one element of xA will have this property, or any connection set that contains all but one element of xA. A connection set that contains exactly two elements y1 and y2 of xA will have this property if and only if y−11 y2 is a square in A. It would be nice to completely characterise the Cayley graphs on Dih(A,x) that are also Cayley on A×C2. This would, however, require a fairly deep understanding of the full automorphism group of any such graph (for example, whether or not the cosets of A are blocks of imprimitivity for the automorphism group will be important) that is beyond the scope of this project. Acknowledgment: The authors thank the anonymous referees for helpful comments on this paper. References [1] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci. Hungar. 29 (1977) 329–336. [2] E. Dobson, Isomorphism problem for Cayley graphs of Z3p, Discrete Math. 147 (1995) 87–94. [3] E. Dobson, On the Cayley isomorphism problem, Discrete Math. 247(1-3) (2002) 107–116. [4] E. Dobson, Automorphism groups of metacirculant graphs of order a product of two distinct primes, Combin. Probab. Comput. 15(1-2) (2006) 105–130. [5] E. Dobson, J. Morris, Cayley graphs of more than one abelian group, arXiv:1505.05771. [6] E. Dobson, D. Witte, Transitive permutation groups of prime-squared degree, J. Algebraic Combin. 16 (2002) 43–69. [7] A. Joseph, The isomorphism problem for Cayley digraphs on groups of prime-squared order, Discrete Math. 141(1-3) (1995) 173–183. 56 https://doi.org/10.1007/BF01895854 https://doi.org/10.1007/BF01895854 https://doi.org/10.1016/0012-365X(95)00099-I https://doi.org/10.1016/S0012-365X(01)00164-9 https://doi.org/10.1017/S0963548305007066 https://doi.org/10.1017/S0963548305007066 https://arxiv.org/abs/1505.05771 https://doi.org/10.1023/A:1020882414534 https://doi.org/10.1023/A:1020882414534 https://doi.org/10.1016/0012-365X(93)E0215-P https://doi.org/10.1016/0012-365X(93)E0215-P J. Morris, J. Smolčić / J. Algebra Comb. Discrete Appl. 8(1) (2021) 53–57 [8] I. Kovács, M. Servatius, On Cayley digraphs on nonisomorphic 2-groups, J. Graph Theory 70(4) (2012) 435–448. [9] C. H. Li, On isomorphisms of finite Cayley graphs–a survey, Discrete Math. 256(1-2) (2002), 301–334. [10] C. H. Li, Z. P. Lu, P. Palfy, Further restrictions on the structure of finite CI-groups, J. Algebr. Comb. 26 (2007) 161–181. [11] D. Marušič, J. Morris, Normal circulant graphs with noncyclic regular subgroups, J. Graph Theory 50(1) (2005) 13–24. [12] L. Morgan, J. Morris, G. Verret, Digraphs with small automorphism groups that are Cayley on two nonisomorphic groups, The Art of Discrete and Applied Mathematics 3 (2020) #P1.01. [13] J. Morris, Isomorphic Cayley graphs on different groups, Proceedings of the Twenty-seventh South- eastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA) 121 (1996) 93–96. [14] J. Morris, Isomorphic Cayley graphs on nonisomorphic groups, J. Graph Theory 31(4) (1999) 345– 362. [15] M. Muzychuk, On the isomorphism problem for cyclic combinatorial objects, Discrete Math. 197/198 (1999) 589–606. [16] M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc. 88 (2004) 1–41. 57 https://doi.org/10.1002/jgt.20625 https://doi.org/10.1002/jgt.20625 https://doi.org/10.1016/S0012-365X(01)00438-1 https://doi.org/10.1007/s10801-006-0052-1 https://doi.org/10.1007/s10801-006-0052-1 https://doi.org/10.1002/jgt.20088 https://doi.org/10.1002/jgt.20088 https://doi.org/10.26493/2590-9770.1254.266 https://doi.org/10.26493/2590-9770.1254.266 https://doi.org/10.1002/(SICI)1097-0118(199908)31:4%3C345::AID-JGT9%3E3.0.CO;2-V https://doi.org/10.1002/(SICI)1097-0118(199908)31:4%3C345::AID-JGT9%3E3.0.CO;2-V https://doi.org/10.1016/S0012-365X(99)90119-X https://doi.org/10.1016/S0012-365X(99)90119-X https://doi.org/10.1112/S0024611503014412 https://doi.org/10.1112/S0024611503014412 Introduction The families References