On the Automorphism Groups of Regular Hyper-Stars and Folded Hyper-Stars

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.

to appear in Ars Combinatoria