The automorphism group of the s-stable Kneser graphs

Abstract

For k,s≥2, the s-stable Kneser graphs are the graphs with vertex set the k-subsets S of {1,…,n} such that the circular distance between any two elements in S is at least s and two vertices are adjacent if and only if the corresponding k-subsets are disjoint. Braun showed that for n≥2k+1 the automorphism group of the 2-stable Kneser graphs (Schrijver graphs) is isomorphic to the dihedral group of order 2n. In this paper we generalize this result by proving that for s≥2 and n≥sk+1 the automorphism group of the s-stable Kneser graphs also is isomorphic to the dihedral group of order 2n.