Sparse Kneser graphs are Hamiltonian

DOI10.1112/JLMS.12406zbMath1470.05096OpenAlexW2952494337MaRDI QIDQ5006324

Torsten Mütze, Bartosz Walczak, Jerri Nummenpalo

Publication date: 13 August 2021

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/jlms.12406

zbMATH Keywords

vertex-transitive graphHamilton cycleodd graph

Mathematics Subject Classification ID

Combinatorial codes (94B25) Eulerian and Hamiltonian graphs (05C45) Density (toughness, etc.) (05C42)

Related Items (2)

Large cycles in generalized Johnson graphs ⋮ Gray codes and symmetric chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Long cycles in the middle two layers of the discrete cube
• An inductive construction for Hamilton cycles in Kneser graphs
• Kneser's conjecture, chromatic number, and homotopy
• Universal cycles for permutations
• Hamiltonian uniform subset graphs
• A short proof of Kneser's conjecture
• Triangle-free Hamiltonian Kneser graphs
• Hamiltonian Kneser graphs
• Generalized Kneser coloring theorems with combinatorial proofs
• Shorthand universal cycles for permutations
• Explicit 2-factorizations of the odd graph
• A framework for constructing de Bruijn sequences via simple successor rules
• The Rugby footballers of Croam
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• A combinatorical proof of Kneser's conjecture
• Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues
• A constant-time algorithm for middle levels Gray codes
• The footballers of Croam
• Constructions via Hamiltonian theorems
• Proof of the middle levels conjecture
• Perfect Snake-in-the-Box Codes for Rank Modulation
• Computing All Maps into a Sphere
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• A Survey of Combinatorial Gray Codes
• A New Short Proof of Kneser's Conjecture
• A short proof of the middle levels theorem
• Solving the Sigma-Tau Problem
• Reducibility among Combinatorial Problems
• Extending continuous maps
• Bipartite Kneser graphs are Hamiltonian
• A minimum-change version of the Chung-Feller theorem for Dyck paths

This page was built for publication: Sparse Kneser graphs are Hamiltonian