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 $FQ_n$ is the Cayley graph Cay$(\mathbb{Z}_2^n,S)$, where $S=\{e_1,e_2,\dots,e_n\}\cup 
\{u=e_1+e_2+\dots+e_n\}$, and $e_i = (0,\dots, 0, 1, 0,$ $\dots, 0)$, with 1 at the $i$th position, $1\leq i \leq n$. In this paper, we show that the folded hypercube $FQ_n$ is a distance-transitive graph. Then, we study some properties of this graph. In particular, we show that if $n\geq 4$ is an even integer, then the folded hypercube $FQ_n$ is an $automorphic$ graph, that is, $FQ_n$ is a distance-transitive primitive graph which is not a complete or a line graph.

Keywords

Main Subjects

References

[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
Communications in Combinatorics and Optimization
Volume 10, Issue 1
March 2025
Pages 207-217

Files

Share

How to cite

Statistics