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

From MaRDI portal
scientific article
Language Label Description Also known as
English
An inductive construction for Hamilton cycles in Kneser graphs
scientific article

    Statements

    An inductive construction for Hamilton cycles in Kneser graphs (English)
    0 references
    0 references
    18 October 2011
    0 references
    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.
    0 references

    Identifiers