On the symmetries of some classes of recursive circulant graphs

Document Type: Research Paper


Lorestan University


A recursive-circulant $G(n; d)$ is defined to be a‎ ‎circulant graph with $n$ vertices and jumps of powers of $d$‎.
‎$G(n; d)$ is vertex-transitive‎, ‎and has some strong hamiltonian‎ ‎properties‎. ‎$G(n;d)$ has a recursive structure when $n = cd^m$‎, ‎$1 \leq c < d $ [Theoret‎. ‎Comput‎. ‎Sci. 244 (2000) 35-62]‎. ‎In this paper‎, ‎we will find the automorphism‎ ‎group of some classes of recursive-circulant graphs‎. ‎In particular‎, ‎we‎ ‎will find that the automorphism group of $G(2^m; 4)$ is isomorphic‎ ‎with the group $D_{2 \cdot 2^m}$‎, ‎the dihedral group of order $2^{m+1}$‎.


Main Subjects

S. B. Akers and B. Krishnamurthy (1989). A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput.. 38 (4), 555-566
C. H. Tsai, Jimmy J. M. Tan and L. H. Hsu (2004). The super-connected property of recursive circulant graphs. Inform. Process. Lett.. 91, 293-298
N. L. Biggs (1993). Algebraic Graph Theory. (Second edition), Cambridge University Press, Cambridge.
Y. Q. Feng (2006). Automorphism groups of Cayley graphs on symmetric groups with generating transposition. J. Combin. Theory Ser. B. 96, 67-72
A. Ganesan Automorphisms of Cayley graphs generated by transposition sets. Preprint is at href{http://arxiv.org/abs/1303.5974v2}{http://arxiv.org/abs/1303.5974v2}.
C. Godsil and G. Royle (2001). Algebraic Graph Theory. Graduate Texts in Mathematics, {bf 207}, Springer-Verlag, New York.
C. D. Godsil (1981). On the full automorphism group of a graph. Combinatorica. 1, 243-256
S. M. Mirafzal On the automorphism groups of regular hyper-stars and folded hyper-stars. Ars Combinatoria (in press).
S. M. Mirafzal Some other algebraic properties of folded hypercubes. Ars Combinatoria (in press).
J. H. Park and K. Y. Chwa (2000). Fundamental study recursive circulants and their embedding among hypercubes. Theoret. Comput. Sci.. 244, 35-62
J. J. Rotman (1995). An Introduction to the Theory of Groups. 4th ed., Springer-Verlag, New York. 148
J. X. Zhou (2011). The automorphism group of the alternating group graph. Appl. Math. Lett.. 24 (2), 229-231