On the distance-transitivity of the folded hypercube

Document Type : Original paper


Lorestan university


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.


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.
[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.
[5] M. Ghasemi, Some results about the reliability of folded hypercubes, Bull. Malays. Math. Sci. Soc. 44 (2021), 1093–1099.
[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.
[8] L. Lu and Q. Huang, Automorphisms and isomorphisms of enhanced hypercubes, Filomat 34 (2020), no. 8, 2805–2812.
[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.
[11] S.M. Mirafzal, Some other algebraic properties of folded hypercubes, Ars Combin. 124 (2011), 153–159.
[12] S.M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proc. Math. Sci. 129 (2019), Article number: 34.
[13] S.M. Mirafzal, On the automorphism groups of connected bipartite irreducible graphs, Proc. Math. Sci. 130 (2020), Article number: 57.
[14] S.M. Mirafzal, Some remarks on the square graph of the hypercube, Ars Math. Contemp. 23 (2023), no. 2, 2–6.
[15] S.M. Mirafzal, Some algebraic properties of the subdivision graph of a graph, Commun. Comb. Optim. (In press), https://doi.org/10.22049/cco.2023.28270.1494
[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.
[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.
[20] J.J. Rotman, An Introduction to the Theory of Groups, vol. 148, Springer Science & Business Media, New York, 2012.
[21] E. Sabir and J. Meng, Structure fault tolerance of hypercubes and folded hypercubes, Theoret. Comput. Sci. 711 (2018), 44–55.
[22] J.M. Xu, Topological Structure and Analysis of Interconnection Networks, vol. 7, Springer Science & Business Media, New York, 2013.
[23] J.M. Xu and M. Ma, Cycles in folded hypercubes, Appl. Math. Lett. 19 (2006), no. 2, 140–145.
[24] M.M. Zhang and J.X. Zhou, On g-extra connectivity of folded hypercubes, Theoret. Comput. Sci. 593 (2015), 146–153.