Two families of graphs that are Cayley on nonisomorphic groups

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.

Keywords

• Cayley graphs
• Nonisomorphic groups
• Cayley on nonisomorphic groups

References

1. [1] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci. Hungar. 29 (1977) 329–336.
2. [2] E. Dobson, Isomorphism problem for Cayley graphs of Z3 p, Discrete Math. 147 (1995) 87–94.
3. [3] E. Dobson, On the Cayley isomorphism problem, Discrete Math. 247(1-3) (2002) 107–116.
4. [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. [5] E. Dobson, J. Morris, Cayley graphs of more than one abelian group, arXiv:1505.05771.
6. [6] E. Dobson, D. Witte, Transitive permutation groups of prime-squared degree, J. Algebraic Combin. 16 (2002) 43–69.
7. [7] A. Joseph, The isomorphism problem for Cayley digraphs on groups of prime-squared order, Discrete Math. 141(1-3) (1995) 173–183.
8. [8] I. Kovács, M. Servatius, On Cayley digraphs on nonisomorphic 2-groups, J. Graph Theory 70(4) (2012) 435–448.

9. [9] C. H. Li, On isomorphisms of finite Cayley graphs–a survey, Discrete Math. 256(1-2) (2002), 301–334.
10. [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. [11] D. Marušic, J. Morris, Normal circulant graphs with noncyclic regular subgroups, J. Graph Theory 50(1) (2005) 13–24.
12. [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. [13] J. Morris, Isomorphic Cayley graphs on different groups, Proceedings of the Twenty-seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA) 121 (1996) 93–96.
14. [14] J. Morris, Isomorphic Cayley graphs on nonisomorphic groups, J. Graph Theory 31(4) (1999) 345– 362.
15. [15] M. Muzychuk, On the isomorphism problem for cyclic combinatorial objects, Discrete Math. 197/198 (1999) 589–606.
16. [16] M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc. 88 (2004) 1–41.