On the Automorphism Groups of Regular Hyperstars and Folded Hyperstars

Abstract

The hyper-star graph $HS(n,k)$ is defined as follows: its vertex-set is the set of $\{0,1\}$-sequences of length $n$ with weight $k$, where the weight of a sequence $v$ is the number of $1$s in $v$, and two vertices are adjacent if and only if one can be obtained from the other by exchanging the first symbol with a different symbol ($1$ with $0$, or $0$ with $1$) in another position. In this paper, we will find the automorphism groups of regular hyper-star and folded hyper-star graphs. Then, we will show that only the graphs $HS(4,2)$ and $FHS(4,2)$ are Cayley graphs.