An Inductive Construction for Hamilton Cycles in Kneser Graphs

Abstract

The Kneser graph $K(n,r)$ has as vertices all $r$-subsets of an $n$-set with two vertices adjacent if the corresponding subsets are disjoint. It is conjectured that, except for $K(5,2)$, these graphs are Hamiltonian for all $n\geq 2r+1$. In this note we describe an inductive construction which relates Hamiltonicity of $K(2r+2s,r)$ to Hamiltonicity of $K(2r'+s,r')$. This shows (among other things) that Hamiltonicity of $K(2r+1,r)$ for all $3\leq r\leq k$ implies Hamiltonicity of $K(2r+2,r)$ for all $r\leq 2k+1$. Applying this result extends the range of values for which Hamiltonicity of $K(n,r)$ is known. Another consequence is that certain families of Kneser graphs ($K(\frac{27}{13}r,r)$ for instance) contain infinitely many Hamiltonian graphs.