Title

# ON ISOMORPHISMS OF FINITE CAYLEY GRAPHS

Alternative Title

Author
Name pinyin
JIA Zhen
School number
12032851
Degree

Discipline
0701 数学
Subject category of dissertation
07 理学
Supervisor

Mentor unit

Publication Years
2022-05-09
Submission date
2022-06-21
University

Place of Publication

Abstract

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.

Other Abstract

(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是不同的素数。

(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。

Keywords
Language
English
Training classes

Enrollment Year
2020
Year of Degree Awarded
2022-06
References List

[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.

Domestic book classification number
O15
Data Source

Document TypeThesis
Identifierhttp://kc.sustech.edu.cn/handle/2SGJ60CL/343178
DepartmentDepartment of Mathematics
Recommended Citation
GB/T 7714
Jia Z. ON ISOMORPHISMS OF FINITE CAYLEY GRAPHS[D]. 深圳. 南方科技大学,2022.
 Files in This Item: File Name/Size DocType Version Access License 12032851-贾震-数学系.pdf（901KB） Restricted Access -- Fulltext Requests
 Related Services Recommend this item Bookmark Usage statistics Export to Endnote Export to Excel Export to Csv Altmetrics Score Google Scholar Similar articles in Google Scholar [贾震]'s Articles Baidu Scholar Similar articles in Baidu Scholar [贾震]'s Articles Bing Scholar Similar articles in Bing Scholar [贾震]'s Articles Terms of Use No data! Social Bookmark/Share