Kneser graphs are Hamiltonian for \(n\geq 3k\)

DOI10.1006/jctb.2000.1969zbMath1024.05055OpenAlexW1973089617WikidataQ29398606 ScholiaQ29398606MaRDI QIDQ1850485

Ya-Chen Chen

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.2000.1969

zbMATH Keywords

Hamiltonian cyclesGray codeuniform subset graphantipodal layer problemErdős revolving door problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items (22)

Sperner type theorems with excluded subposets ⋮ Set labelling vertices to ensure adjacency coincides with disjointness ⋮ On the connectivity of the disjointness graph of segments of point sets in general position in the plane ⋮ Disjointness graphs of segments in \(\mathbb{R}^2\) are almost all Hamiltonian ⋮ On the boxicity of Kneser graphs and complements of line graphs ⋮ On the central levels problem ⋮ Triangle-free Hamiltonian Kneser graphs ⋮ Arrangements of \(k\)-sets with intersection constraints ⋮ Bipartite Kneser graphs are Hamiltonian ⋮ Bipartite Kneser graphs are Hamiltonian ⋮ Unnamed Item ⋮ Existence of a \(P_{2 k + 1}\)-decomposition in the Kneser graph \(K G_{t, 2}\) ⋮ A new class of transitive graphs ⋮ Claw-decomposition of Kneser Graphs ⋮ A minimum-change version of the Chung-Feller theorem for Dyck paths ⋮ Short proof that Kneser graphs are Hamiltonian for \(n \geqslant 4k\) ⋮ Diameters of uniform subset graphs ⋮ Graphs as navigational infrastructure for high dimensional data spaces ⋮ A constant-time algorithm for middle levels Gray codes ⋮ Sparse Kneser graphs are Hamiltonian ⋮ Decomposition of the Kneser graph into paths of length four ⋮ Spectrum of Johnson graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hamiltonian uniform subset graphs
• Two Hamilton cycles in bipartite reflective Kneser graphs
• The antipodal layers problem
• Monotone Gray codes and the middle levels problem
• The Rugby footballers of Croam
• Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues
• A note on Hamiltonian circuits

This page was built for publication: Kneser graphs are Hamiltonian for \(n\geq 3k\)