An inductive construction for Hamilton cycles in Kneser graphs (Q640449)

Summary: 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({27\over 13},r,r)\) for instance) contain infinitely many Hamiltonian graphs.