An inductive construction for Hamilton cycles in Kneser graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
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.
@article{10_37236_676,
author = {J. Robert Johnson},
title = {An inductive construction for {Hamilton} cycles in {Kneser} graphs},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/676},
zbl = {1230.05181},
url = {http://geodesic.mathdoc.fr/articles/10.37236/676/}
}
J. Robert Johnson. An inductive construction for Hamilton cycles in Kneser graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/676
Cité par Sources :