ON ISOMORPHISMS OF FINITE CAYLEY GRAPHS

This thesis is a survey on the isomorphism problem of Cayley graphs, especially on relevant results of CI-groups. The isomorphism of Cayley graphs is an important problem in the research of Cayley graphs. For the isomorphism problem of Cayley graphs, we can firstly study Cayley graphs of the same group. A group 𝐺 is called a CI-group if all Cayley graphs 
of 𝐺 are CI-graphs. Therefore, finding all CI-groups can partially solve the isomorphism problem of Cayley graphs. Through the study of CI-groups, we can have a better understanding of Cayley graphs. In this thesis, we summarize some known CI-groups as follows: 
(1) ℤ_n where n∈{8,9,18} or n=k, 2k or 4k, where k is odd and square-free; 
(2) ℤ_p,  ℤ^2_p,  ℤ^3_p, ℤ^4_p, ℤ^5_p, where p is a prime; 
(3) ℤ^2_2×ℤ_3,  ℤ^5_2,  ℤ^3_2×ℤ_3,  ℤ_9×ℤ_4,  ℤ^2_2×ℤ_9;
(4) Q_8, A_4, ℤ_3⋊ℤ_4,  ℤ^2_3⋊ℤ_2,  𝐷_18,  𝐷_2p, where p is a prime; 
(5) 〈a,b|a^p=b^4=1, a^b=a^−1〉 and 〈a,b|a^p=b^8=1, a^b=a^−1〉; 
(6) ℤ_p×ℤ^3_2, ℤ_p×ℤ^5_2, ℤ_p×𝑄_8, and ℤ^2_p×ℤ_4; 
(7) ℤ_p×ℤ_q,  ℤ^2_p×ℤ_q, ℤ^3_p×ℤ_q, ℤ^4_p×ℤ_q, where p,q are distinct primes. 

In addition, a breakthrough result on DCI-groups is to give a description of 𝑚-DCI groups which 
are contained in 𝒟𝒞ℐ(𝑚). Let 𝒟𝒞ℐ(𝑚) be the set of the finite group 𝐺 satisfying the follows: 
(1) 𝐺 is the direct product of 𝑈 and 𝑉 satisfying that (i) (|𝑈|,|𝑉|) =1 and |𝑈| is odd; 
(ii) 𝑈 is abelian and 𝑉 is one of the following groups: 1, 𝑄_8, 𝐴_4, 𝐴_5, 
𝑄_8⋊ℤ_3, ℤ^2_3⋊𝑄_8, ℤ^t_2, ℤ_2^t,  or 𝐸(𝑀,2^t) where 𝑡⩾1. 
(2) The Sylow 𝑝-subgroup of 𝐺 is homocyclic or 𝑄_8.

It's proved in[1] that 𝒟𝒞ℐ(𝑚) contains all 𝑚-DCI-groups. There is a natural problem to determine which groups in 𝒟𝒞ℐ(𝑚) are 𝑚-DCI-groups.  Li[2] shows that all members in 𝒟𝒞ℐ(2) are indeed 2-DCI-groups. Through the study of 2-DCI-groups and Tutte's theorem, we generalize some results under special condition to 3-DCI-groups. 

凯莱图的同构问题是凯莱图研究中一个重要问题。对于凯莱图同构问题，可以先研究在同一个群下的情况。 CI-群便是满足其所有同构的凯莱图之间只相差一个凯莱映射的群。因此，找到所有的 CI-群便可以部分地解决凯莱图同构问题。通过对 CI-群的研究，我们能对凯莱图有更深刻地认识。在本文中，我们总结一些已知的 CI-群如下： 
(1) Z_n，此时n在 {8,9,18}中或者n=2^m×k，这里0= (2) Z^2_p，Z^3_p，Z^4_p，Z^5_p，这里p是素数。 
(3) Z^2_2×Z_3， Z^5_2，Z^3_2×Z_3，Z_9×Z_4，Z^2_2×Z_9。 
(4) Q_8，A_4，Z_3×Z_4，Z^2_3:Z_2，D_18，D_2p。 
(5) Z_p:Z_4，此时其中心的阶为 2； Z_p:Z_8，此时其中心的阶为 4。 
(6) Z_p×Z^3_2，Z_p×Z^5_2，Z_p×Q_8，Z^2_p×Z_4。 
(7) Z_p×Z_q，Z^2_p×Z_q，Z^3_p×Z_q，和 Z^4_p×Z_q，这里p和q是不同的素数。

此外，CI-群上的一个突破性的结果，便是给出了 m-DCI群的一个刻画DCI(m)。 DCI(m)是满足下面性质的一类群的集合： 
(1) G是U和V的直积满足：(i) (|U|,|V|)=1；(ii) U是奇数阶的交换群，V是下面群中的一个：1，Q_8，A_4，A_5，Q_8:Z_3，Z^2_3:Q_8，Z^t_2，Z_2^t，E(M,2^t)，这里t>=1。 
(2) G的西罗p群是同阶循环的或者是Q_8。
在论文 [1]中，我们知道DCI(m)包含所有的m-DCI群。接下来我们想知道DCI(m)中哪些群确实是m-DCI群。李才恒教授在[2]中证明了DCI(2)中的群确实都是 2-DCI群。通过对 2-DCI群和 Tutte定理的学习，在本文中我们将部分结果推广到 3-DCI群上。

[1] Brian Alspach. Graph Symmetry: Algebraic Methods and Applications[M]. Springer Netherlands,1997.
[2] Brian Alspach and Lewis A. Nowitz. Elementary proofs that 𝑍^2_𝑝 and 𝑍^3_𝑝are CI-groups[J]. Eur. J. Comb., 20:607–617, 1999.
[3] László Babai. Isomorphism problem for a class of point-symmetric structures[J/OL]. Acta Math. Acad. Sci. Hungar., 29(3-4):329–336, 1977.
[4] László Babai. Automorphism groups, isomorphism, reconstruction[M]. In Handbook of combinatorics, Vol. 1, 2, pages 1447–1540. Elsevier Sci. B. V., Amsterdam, 1995.
[5] László Babai and Peter Frankl. Isomorphisms of Cayley graphs. I[C]. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, volume 18 of Colloq. Math. Soc. János Bolyai, pages 35–52. North-Holland, Amsterdam-New York, 1978.
[6] László Babai and Peter Frankl. Isomorphisms of Cayley graphs. II[J/OL]. Acta Math. Acad. Sci. Hungar., 34(1-2):177–183, 1979.
[7] Gregory L. Cherlin and Ulrich Felgner. Homogeneous solvable groups[J/OL]. J. London Math. Soc.(2), 44(1):102–120, 1991.
[8] Leonard Eugene Dickson. Linear groups: With an exposition of the Galois field theory[M]. Dover Publications, Inc., New York, 1958.
[9] Edward Dobson. Isomorphism problem for Cayley graphs of 𝑍^3_𝑝 [J]. Discrete Math., 147(1-3):87–94, 1995.
[10] Edward Dobson and Pablo Spiga. CI-groups with respect to ternary relational structures: new examples[J/OL]. Ars Math. Contemp., 6(2):351–364, 2013.
[11] Bernard Elspas and James Turner. Graphs with circulant adjacency matrices[J]. J. Combinatorial Theory, 9:297–307, 1970.
[12] Yan Quan Feng and István KovÁcs. Elementary abelian groups of rank 5 are DCI-groups[J/OL]. J. Combin. Theory Ser. A, 157, 05 2017.
[13] Chris Godsil. On the full automorphism group of a graph[J/OL]. Combinatorica, 1(3):243–256,1981.
[14] Chris Godsil. On Cayley graph isomorphisms[J]. Ars Combin., 15:231–246, 1983.
[15] Chris Godsil and Gordon F. Royle. Algebraic Graph Theor[M]. Number Book 207 in Graduate Texts in Mathematics. Springer, 2001.
[16] Fletcher Gross. Conjugacy of odd order Hall subgroups[J/OL]. Bull. London Math. Soc., 19(4):311–319, 1987.
[17] Zheng Yu Gu and Cai Heng Li. A nonabelian CI-group[J/OL]. Australas. J. Combin., 17:229–233, 1998.
[18] Robert M. Guralnick. Subgroups of prime power index in a simple group[J/OL]. J. Algebra, 81(2):304–311, 1983.
[19] Geňa Hahn and Claude Tardif. Graph homomorphisms: structure and symmetry[M]. In Graph symmetry (Montreal, PQ, 1996), volume 497 of NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., pages 107–166. Kluwer Acad. Publ., Dordrecht, 1997.
[20] Mitsugu Hirasaka and Mikhail Muzychuk. An elementary abelian group of rank 4 is a CIgroup[J/OL]. J. Combin. Theory Ser. A, 94:339–362, 05 2001.
[21] István Kovács and Mikhail Muzychuk. The group 𝑍^2_p×𝑍_𝑞 is a CI-group[J/OL]. Comm. Algebra, 37(10):3500–3515, 2009.
[22] István Kovács and Grigory Ryabov. The group 𝐶^4_𝑝 × 𝐶_𝑞 is a DCI-group[J]. Discrete Math., 345:112705, 03 2022.
[23] Cai Heng Li. On isomorphisms of connected Cayley graphs. II[J/OL]. J. Combin. Theory Ser. B, 74(1):28–34, 1998.
[24] Cai Heng Li. Finite CI-groups are soluble[J/OL]. Bull. London Math. Soc., 31(4):419–423, 1999.
[25] Cai Heng Li. Isomorphisms of finite Cayley digraphs of bounded valency. II[J/OL]. J. Combin. Theory Ser. A, 87(2):333–346, 1999.
[26] Cai Heng Li. On isomorphisms of finite Cayley graphs—a survey[J/OL]. Discrete Math., 256(1):301–334, 2002.
[27] Cai Heng Li, Zai Ping Lu, and P. P. Pálfy. Further restrictions on the structure of finite CIgroups[J/OL]. J. Algebraic Combin., 26(2):161–181, 2007.
[28] Cai Heng Li and Cheryl E. Praeger. The finite simple groups with at most two fusion classes of every order[J/OL]. Comm. Algebra, 24(11):3681–3704, 1996.
[29] Cai Heng Li and Cheryl E. Praeger. Finite groups in which any two elements of the same order are either fused or inverse-fused[J/OL]. Comm. Algebra, 25(10):3081–3118, 1997.
[30] Cai Heng Li and Cheryl E. Praeger. On the isomorphism problem for finite Cayley graphs of bounded valency[J/OL]. European J. Combin., 20(4):279–292, 1999.
[31] Cai Heng Li, Cheryl E. Praeger, and Ming Yao Xu. Isomorphisms of finite Cayley digraphs of bounded valency[J/OL]. J. Combin. Theory Ser. B, 73(2):164–183, 1998.
[32] Joy Morris. Elementary proof that 𝑍^4_𝑝 is a DCI-group[J]. Discrete Math., 338, 2015.
[33] Mikhail E. Muzychuk. Adám’s conjecture is true in the square-free case[J]. J. Comb. Theory, Ser. A, 72:118–134, 1995.
[34] Mikhail E. Muzychuk. On Adám’s conjecture for circulant graphs[J]. Discrete Math., 167-168:497–510, 1997.
[35] Mikhail E. Muzychuk. An elementary abelian group of large rank is not a CI-group[M/OL]. volume 264, pages 167–185. 2003.
[36] Lewis A. Nowitz. A non-Cayley-invariant Cayley graph of the elementary abelian group of order 64[J]. Discrete Math., 110(1-3):223–228, 1992.
[37] Cheryl E. Praeger. Imprimitive symmetric graphs[J/OL]. Ars Combin., 19(A):149–163, 1985.
[38] Cheryl E. Praeger and Csaba Schneider. Permutation groups and Cartesian decompositions[M]. Number Book 449 in London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2018.
[39] Joseph J. Rotman. An introduction to the theory of groups[M]. Number Book 148 in Graduate Texts in Mathematics. Springer-Verlag, New York, fourth edition, 1995.
[40] Grigory Ryabov. The Cayley isomorphism property for the group 𝐶^5_2 × 𝐶_𝑝[J/OL]. Ars Math. Contemp., 19(2):277–295, 2020.
[41] Grigory Ryabov. The Cayley isomorphism property for the group 𝐶_4 × 𝐶^2_𝑝 [J/OL]. Comm. Algebra, 49(4):1788–1804, 2021.
[42] Gábor Somlai. The Cayley isomorphism property for groups of order 8𝑝[J/OL]. Ars Math. Contemp., 8(2):433–444, 2015.
[43] Gábor Somlai and Mikhail Muzychuk. The Cayley isomorphism property for 𝑍^3_𝑝× 𝑍_𝑞[J/OL]. Algebr. Comb., 4(2):289–299, 2021.
[44] Michio Suzuki. Group theory. I[M]. Iwanami Shoten, Tokyo, 1977.
[45] Michio Suzuki. Group theory. II[M]. Springer-Verlag, New York, 1986.
[46] Shunichi Toida. A note on Adám’s conjecture[J/OL]. J. Combin Theory Ser. B, 23(2-3):239–246, 1977.
[47] Ming Yao Xu. On isomorphisms of Cayley digraphs and graphs of groups of order 𝑝3[J]. Advances Math (China), 17:427–428, 1988.
[48] Ji Ping Zhang. On finite groups all of whose elements of the same order are conjugate in their automorphism groups[J/OL]. J. Algebra, 153(1):22–36, 1992.
[49] 徐明曜. 有限群初步[M]. 现代数学基础丛书152. 科学出版社第一版, 2019.