Automorphisms and isomorphisms of enhanced hypercubes

Abstract

Let $Z_2^n$ be the elementary abelian $2$-group, which can be viewed as the vector space of dimension $n$ over $F_2$. Let $\{e_{1},\ldots,e_{n}\}$ be the standard basis of $Z_{2}^{n}$ and $\epsilon_k=e_{k}+\cdots+e_n$ for some $1\le k\le n-1$. Denote by $\Gamma_{n,k}$ the Cayley graph over $Z_2^n$ with generating set $S_k=\{e_1,\ldots,e_n,\epsilon_k\}$, that is, $\Gamma_{n,k}=Cay(Z_2^n,S_k)$. In this paper, we characterize the automorphism group of $\Gamma_{n,k}$ for $1\le k\le n-1$ and determine all Cayley graphs over $Z_2^n$ isomorphic to $\Gamma_{n,k}$. Furthermore, we prove that for any Cayley graph $\Gamma=Cay(Z_2^n,T)$, if $\Gamma$ and $\Gamma_{n,k}$ share the same spectrum, then $\Gamma\cong \Gamma_{n,k}$. Note that $\Gamma_{n,1}$ is known as the so called $n$-dimensional folded hypercube $FQ_n$, and $\Gamma_{n,k}$ is known as the $n$-dimensional enhanced hypercube $Q_{n,k}$.