Two families of graphs that are Cayley on nonisomorphic groups
Two families of graphs that are Cayley on nonisomorphic groups
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.
___
- [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 Z3
p, 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.
- [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šic, 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 Southeastern
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.