On the Cayley graphs of symmetric group $S_4$

Raei, Fatemeh

doi:10.22103/jmmr.2025.24333.1720

On the Cayley graphs of symmetric group $S_4$

Document Type : Research Paper

Author

Fatemeh Raei

Department of Mathematics Education, Farhangian University, P.O. Box 14665-889, Tehran, Iran

10.22103/jmmr.2025.24333.1720

Abstract

Let $S_n$ be the symmetric group of degree $n$. In this paper, we classify non-isomorphic Cayley graphs of $S_4$ of valency 3. Moreover, we verify that there are exactly 10 non-isomorphic Cayley graphs of $S_4$ with valency 3. Also, we classify the valency 3 CI-graphs of Cayley graphs of $S_4$ and we prove that $S_4$ is not a CI-group and does not possess the $3$-CI-property. We show that there are at least 10 non-isomorphic Cayley graphs of the symmetric group $S_n$ with valency 3.

Keywords

Cayley graph

Symmetric group

Isomorphism

Subjects

Combinatorics, Graph, Coding and Cryptography

[1] Adiga, C., and Ariamanesh, H. (2012). Some properties of Cayley graphs on symmetric groups Sn, International Journal of Algebra, 6(17), 807-813.

[2] Li, C. H. (2002). On isomorphisms of nite Cayley graphs- a survey, Discrete Mathematics, 256, 301-334.

[3] Cheng, E., & Lipt´ak, L. (2007). Fault resiliency of Cayley graphs generated by transpositions, Internat. J. Found Comput. Sci., 18, 1005-1022.

[4] Dehmer, M. Li, X., & Shi, Y. (2015). Connections between generalized graph entropies and graph energy. Complexity, 21, 35-41.

[5] Fadzil, A. F. A., Sarmin, N. H. & Erfanian, A. (2020). The energy of Cayley graphs for symmetric groups of order 24. ASM Science Journal, 13, 1-6.

[6] Fadzil, A. F. A., & Sarmin, N. H. (2020). Energy of Cayley Graphs for Alternating Groups. Southeast Asian Bulletin of Mathematics, 44, 795-789.

[7] Feng, Y. D., Xie, Y. T., & Xu, S. J. (2024). The extendability of Cayley graphs generated by transpositions. Discrete Applied Mathematics, 343, 134-139. https://doi.org/10.1016/j.dam.2023.10.023.

[8] GAP { Groups, Algorithms, Programming, Version 4.12.0. (2022). https://www.gap-system.org

[9] Godsil, C., and Royle, G. (2001). Algebraic Graph Theory, Graduate Texts in Mathematics vol. 207, Springer-Verlag, New York.

[10] GRAPH package { A Package for Graph Theory Algorithms, Version 2.2.1. (2023). https://www.gap-system.org/Packages/graph.html

[11] Gu, Z. Y., & Li, C. H. (1998). A Nonabelian CI-group. Australasian Journal of Combinatorics, 17, 229-233.

[12] Susanti, Y. & Erfanian, A. (2024). Prime square order Cayley graph of cyclic groups. Asian-European Journal of Mathematics, 17(2), 2450003. https://doi.org/10.1142/S1793557124500037