Hamiltonicity of Schrijver graphs and stable Kneser graphs

Abstract

For integers $k\ge 1$ and $n\ge 2k+1$, the Schrijver graph $S(n,k)$ has as vertices all $k$-element subsets of $[n]:=\{1,2,\dots ,n\}$ that contain no two cyclically adjacent elements, and an edge between any two disjoint sets. More generally, for integers $k\ge 1$, $s\ge 2$, and $n\ge sk+1$, the $s$-stable Kneser graph $S(n,k,s)$ has as vertices all $k$-element subsets of $[n]$ in which any two elements are in cyclical distance at least $s$. We prove that all the graphs $S(n,k,s)$, in particular Schrijver graphs $S(n,k)=S(n,k,2)$, admit a Hamilton cycle that can be computed in time $\mathcal{O}(n)$ per generated vertex.