Kneser graphs are Hamiltonian for n 3k

DOI10.1006/JCTB.2000.1969zbMATHDBLPOpenAlexWikidataMaRDI QIDQ1850485FDO

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

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)

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\)

Cites work

• scientific article; zbMATH DE number 3838053 (Why is no real title available?)
• scientific article; zbMATH DE number 3916312 (Why is no real title available?)
• scientific article; zbMATH DE number 3478938 (Why is no real title available?)
• scientific article; zbMATH DE number 3600077 (Why is no real title available?)
• scientific article; zbMATH DE number 638692 (Why is no real title available?)
• scientific article; zbMATH DE number 1439443 (Why is no real title available?)
• A note on Hamiltonian circuits
• Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues
• Hamiltonian uniform subset graphs
• Monotone Gray codes and the middle levels problem
• The Rugby footballers of Croam
• The antipodal layers problem
• Two Hamilton cycles in bipartite reflective Kneser graphs

Cited in

(30)

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