Automorphism Group of the Varietal Hypercube Graph

Abstract

The varietal hypercube graph $VQ_n$ ($n\ge 1$) was proposed by Cheng and Chuang (Varietal hypercube—a new interconnection network topology for large scale multicomputer, Proceedings of the International Conference on Parallel and Distributed Systems, pp 703–708, 1994) as a topology for interconnection network that is an improvement over the well-known hypercube network. It was known that $VQ_n$ is a Cayley graph on the group $D_4^s\times {{\mathbb {Z}}}_2^t$, where $n=3s+t$ with $s\ge 0$ and $0\le t\le 2$. In the present paper, we prove that the full automorphism group of the varietal hypercube graph $VQ_n$ is $(D_4^s\times {{\mathbb {Z}}}_2^t) \rtimes (({\mathbb {Z}}_{2}\wr S_s)\times S_t)$. An open problem in the literature is to determine whether a given Cayley graph is normal and the result shows that the varietal hypercube graph $VQ_n$ is a normal Cayley graph on the group $D_4^s\times {{\mathbb {Z}}}_2^t$.