Kneser graphs are Hamiltonian for n 3k

DOI10.1006/JCTB.2000.1969zbMATH Open1024.05055DBLPjournals/jct/Chen00aOpenAlexW1973089617WikidataQ29398606 ScholiaQ29398606MaRDI QIDQ1850485FDOQ1850485

Authors: 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

Recommendations

• Bipartite Kneser graphs are Hamiltonian
• Sparse Kneser graphs are Hamiltonian
• Sparse Kneser graphs are Hamiltonian
• Hamiltonian Kneser graphs
• Short proof that Kneser graphs are Hamiltonian for \(n \geqslant 4k\)

zbMATH Keywords

Gray codeHamiltonian cyclesuniform subset graphantipodal layer problemErdős revolving door problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (28)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850485)