JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 26, No 2 (2007)

Cai Heng Li , Zai Ping Lu and P.P. Pálfy³

³Department of Algebra and Number Theory, E\ddot otv\ddot os University, Budapest, P.O. Box 120, H-1518 Hungary

A group G is called a CI-group if, for any subsets S, T\subset  G, whenever two Cayley graphs Cay( G, S) and Cay( G, T) are isomorphic, there exists an element σ ϵ Aut( G) such that Sσ  = T. The problem of seeking finite CI-groups is a long-standing open problem in the area of Cayley graphs. This paper contributes towards a complete classification of finite CI-groups. First it is shown that the Frobenius groups of order 4 p and 6 p, and the metacyclic groups of order 9 p of which the centre has order 3 are not CI-groups, where p is an odd prime. Then a shorter explicit list is given of candidates for finite CI-groups. Finally, some new families of finite CI-groups are found, that is, the metacyclic groups of order 4 p (with centre of order 2) and of order 8 p (with centre of order 4) are CI-groups, and a proof is given for the Frobenius group of order 3 p to be a CI-group, where p is a prime.

1. A. Ádám, “Research problem 2-10,” J. Combin. Theory 2 (1967), 309.
2. B. Alspach, “Isomorphisms of Cayley graphs on abelian groups,” in Graph Symmetry: Algebraic Methods and Applications, NATO ASI Ser. C, vol. 497, 1997, pp. 1-23.
3. B. Alspach and T.D. Parsons, “Isomorphisms of circulant graphs and digraphs,” Discrete Math. 25 (1979), 97-108.
4. L. Babai, “Isomorphism problem for a class of point-symmetric structures,” Acta Math. Acad. Sci. Hungar. 29 (1977), 329-336.
5. L. Babai and P. Frankl, “Isomorphisms of Cayley graphs I,” in Colloq. Math. Soc. J. Bolyai,
18. Combinatorics, Keszthely, 1976; North-Holland, Amsterdam, 1978, pp. 35-52.
6. L. Babai and P. Frankl, “Isomorphisms of Cayley graphs II,” Acta Math. Acad. Sci. Hungar. 34 (1979), 177-183.
7. M. Conder and C.H. Li, “On isomorphisms for finite Cayley graphs,” European J. Combin. 19 (1998), 911-919.
8. J.D. Dixon and B. Mortimer, Permutation Groups, Springer-Verlag, New York, 1996.
9. D.Z. Djokovic, “Isomorphism problem for a special class of graphs,” Acta Math. Acad. Sci. Hungar. 21 (1970), 267-270.
10. E. Dobson, “Isomorphism problem for Cayley graph of Z3p,” Discrete Math. 147 (1995), 87-94.
11. E. Dobson, “Isomorphism problem for metacirculant graphs of order a product of distinct primes,” Canad. J. Math. 50 (1998), 1176-1188.
12. B. Elspas and J. Turner, “Graphs with circulant adjacency matrices,” J. Combin. Theory 9 (1970), 297-307.
13. C.D. Godsil, “On Cayley graph isomorphisms,” Ars Combin. 15 (1983), 231-246.
14. M. Hirasaka and M. Muzychuk, “The elementary abelian group of odd order and rank 4 is a CI-group,” J. Combin. Theory Ser. A 94(2) (2001), 339-362.
15. B. Huppert, Endliche Gruppen, Springer, Berlin, 1967.
16. C.H. Li, “Finite CI-groups are soluble,” Bull. London Math. Soc. 31 (1999), 419-423.
17. C.H. Li, “On Cayley isomorphism of finite Cayley graphs-A survey,” Discrete Math. 256(1/2) (2002), 301-334.
18. C.H. Li, “The finite primitive permutation groups containing an abelian regular subgroup,” Proc. London Math. Soc. 87(3) (2003), 725-747.
19. C.H. Li and C.E. Praeger, “The finite simple groups with at most two fusion classes of every order,” Comm. Algebra 24 (1996), 3681-3704.
20. C.H. Li and C.E. Praeger, “On finite groups in which any two elements of the same order are fused or inverse-fused,” Comm. Algebra 25 (1997), 3081-3118.
21. C.H. Li and C.E. Praeger, “On the isomorphism problem for finite Cayley graphs of bounded valency,” European J. Combin. 20 (1999), 279-292.
22. M. Muzychuk, “ Ádám's conjecture is true in the square-free case,” J. Combin. Theory (A) 72 (1995), 118-134.
23. M. Muzychuk, “On Ádám's conjecture for circulant graphs,” Discrete Math. 167/168 (1997), 497-510.
24. M. Muzychuk, “An elementary abelian group of large rank is not a CI-group,” Discrete Math. 264(1-3) (2003), 167-185. Springer
25. L.A. Nowitz, “A non Cayley-invariant Cayley graph of the elementary Abelian group of order 64,” Discrete Math. 110 (1992), 223-228.
26. P.P. Pálfy, “On regular pronormal subgroups of symmetric groups,” Acta Math. Acad. Sci. Hungar. 34 (1979), 187-292.
27. P.P. Pálfy, “Isomorphism problem for relational structures with a cyclic automorphism,” European J. Combin. 8 (1987), 35-43.
28. C.E. Praeger, “Finite transitive permutation groups and finite vertex-transitive graphs,” in Graph Symmetry: Algebraic Methods and Applications, NATO ASI Ser. C, 1997, vol. 497 pp. 277- 318.
29. G. Royle, “Constructive enumeration of graphs,” PhD Thesis, University of Western Australia, 1987.