An inductive construction for Hamilton cycles in Kneser graphs

作者：Johnson J Robert^*

来源：Electronic Journal of Combinatorics, 2011, 18(1): P189.

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 >= 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 <= r <= k implies Hamiltonicity of K(2r + 2, r) for all r <= 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/13 r ,r) for instance) contain infinitely many Hamiltonian graphs.

• 出版日期2011-9-20