2024/01/03 by Mütze, Torsten, Namrata
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2401.01681
For integers k≥ 1 and n≥ 2k+1, the Schrijver graph S(n,k) has as vertices all k-element subsets of [n]:=\1,2,…,n\ that contain no two cyclically adjacent elements, and an edge between any two disjoint sets. More generally, for integers k≥ 1, s≥ 2, and n ≥ 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 O(n) per generated vertex.