On the distance-transitivity of the folded hypercube

Document Type : Original paper

Author

Department of Mathematics, Faculty of Basic Science, Lorestan University, Khorramabad, Iran

Abstract

The folded hypercube FQn is the Cayley graph Cay(Z2n,S), where S={e1,e2,,en}{u=e1+e2++en}, and ei=(0,,0,1,0, ,0), with 1 at the ith position, 1in. In this paper, we show that the folded hypercube FQn is a distance-transitive graph. Then, we study some properties of this graph. In particular, we show that if n4 is an even integer, then the folded hypercube FQn is an automorphic graph, that is, FQn is a distance-transitive primitive graph which is not a complete or a line graph.

Keywords

Main Subjects


[1] N. Biggs, Algebraic Graph Theory. 2nd ed., no. 67, Cambridge university press, London, 1993.
[2] D. Boutin, S. Cockburn, L. Keough, S. Loeb, and P. Rombach, Symmetry parameters of various hypercube families, Art Discret. Appl. Math. 6 (2021), no. 2, Article number P2.06. https://doi.org/10.26493/2590-9770.1481.29d
[3] A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer Berlin, 1989.
[4] A. El-Amawy and S. Latifi, Properties and performance of folded hypercubes, IEEE Trans. Parallel Distrib. Syst. 2 (1991), no. 1, 31–42.  https://doi.ieeecomputersociety.org/10.1109/71.80187
[5] M. Ghasemi, Some results about the reliability of folded hypercubes, Bull. Malays. Math. Sci. Soc. 44 (2021), 1093–1099. https://doi.org/10.1007/s40840-020-00999-4
[6] C. Godsil and G.F. Royle, Algebraic Graph Theory, vol. 207, Springer Science & Business Media, New York, 2001.
[7] C.D. Godsil, R.A. Liebler, and C.E. Praeger, Antipodal distance transitive covers of complete graphs, European J. Combin. 19 (1998), no. 4, 455–478. https://doi.org/10.1006/eujc.1997.0190
[8] L. Lu and Q. Huang, Automorphisms and isomorphisms of enhanced hypercubes, Filomat 34 (2020), no. 8, 2805–2812. http://dx.doi.org/10.2298/FIL2008805L
[9] M. Ma and J.M. Xu, Algebraic properties and panconnectivity of folded hypercubes, Ars Combin. 95 (2010), 179–186.
[10] D. Marušič, Bicirculants via imprimitivity block systems, Mediterr. J. Math. 18 (2021), 1–15. https://doi.org/10.1007/s00009-021-01771-z
[11] S.M. Mirafzal, Some algebraic properties of the subdivision graph of a graph, Commun. Comb. Optim. 9, no. 2, 297–307.  https://doi.org/10.22049/cco.2023.28270.1494
[12] S.M. Mirafzal, Some other algebraic properties of folded hypercubes, Ars Combin. 124 (2011), 153–159.
[13] S.M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proc. Math. Sci. 129 (2019), Article number: 34. https://doi.org/10.1007/s12044-019-0477-9
[14] S.M. Mirafzal, On the automorphism groups of connected bipartite irreducible graphs, Proc. Math. Sci. 130 (2020), Article number: 57. https://doi.org/10.1007/s12044-020-00589-1
[15] S.M. Mirafzal, Some remarks on the square graph of the hypercube, Ars Math. Contemp. 23 (2023), no. 2, 2–6. https://doi.org/10.26493/1855-3974.2621.26f
[16] S.M. Mirafzal and A. Zafari, On the spectrum of a class of distance-transitive graphs, Electron. J. Graph Theory Appl. 5 (2017), no. 1, 63–69.  https://dx.doi.org/10.5614/ejgta.2017.5.1.7
[17] S.M. Mirafzal, Some algebraic properties of bipartite Kneser graphs, Ars Combin. 153 (2020), 3–14.
[18] S.M. Mirafzal and M. Ziaee, Some algebraic aspects of enhanced johnson graphs, Acta Math. Univ. Comenian. 88 (2019), no. 2, 257–266.
[19] S.M. Mirafzal and M. Ziaee, A note on the automorphism group of the Hamming graph, Trans. Comb. 10 (2021), no. 2, 129–136.   https://doi.org/10.22108/toc.2021.127225.1817
[20] J.J. Rotman, An Introduction to the Theory of Groups, vol. 148, Springer Science & Business Media, New York, 2012. https://doi.org/10.1007/978-1-4612-4176-8
[21] E. Sabir and J. Meng, Structure fault tolerance of hypercubes and folded hypercubes, Theoret. Comput. Sci. 711 (2018), 44–55. https://doi.org/10.1016/j.tcs.2017.10.032
[22] J.M. Xu, Topological Structure and Analysis of Interconnection Networks, vol. 7, Springer Science & Business Media, New York, 2013. https://doi.org/10.1007/978-1-4757-3387-7
[23] J.M. Xu and M. Ma, Cycles in folded hypercubes, Appl. Math. Lett. 19 (2006), no. 2, 140–145. https://doi.org/10.1016/j.aml.2005.04.002
[24] M.M. Zhang and J.X. Zhou, On g-extra connectivity of folded hypercubes, Theoret. Comput. Sci. 593 (2015), 146–153. https://doi.org/10.1016/j.tcs.2015.06.008