Bipartite Kneser graphs are Hamiltonian

DOI10.1007/S00493-016-3434-6zbMATH Open1399.05135arXiv1503.09175OpenAlexW1945596496MaRDI QIDQ5895045FDOQ5895045

Pascal Su, Torsten Mütze

Publication date: 23 July 2018

Published in: Combinatorica (Search for Journal in Brave)

Abstract: For integers $kgeq1$ and $ngeq2k+1$ the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $[n]:=1,2,ldots,n$ and an edge between any two vertices (=sets) that are disjoint. The bipartite Kneser graph $H(n,k)$ has as vertices all $k$-element and $(n-k)$-element subsets of $[n]$ and an edge between any two vertices where one is a subset of the other. It has long been conjectured that all Kneser graphs and bipartite Kneser graphs except the Petersen graph $K(5,2)$ have a Hamilton cycle. The main contribution of this paper is proving this conjecture for bipartite Kneser graphs $H(n,k)$. We also establish the existence of cycles that visit almost all vertices in Kneser graphs $K(n,k)$ when $n=2k+o(k)$, generalizing and improving upon previous results on this problem.

Full work available at URL: https://arxiv.org/abs/1503.09175

Recommendations

• Bipartite Kneser graphs are Hamiltonian
• scientific article
• Hamiltonian Kneser graphs
• On Hamiltonian bipartite graphs
• scientific article; zbMATH DE number 1289752
• Two Hamilton cycles in bipartite reflective Kneser graphs
• Bipartite graphs with every \(k\)-matching in a Hamiltonian cycle.
• scientific article; zbMATH DE number 11998
• Hamiltonian cycles in bipartite graphs
• Hamiltonicity of bipartite biclaw-free graphs

zbMATH Keywords

hypercubeHamiltonian cycleKneser graphbipartite Kneser graph

Mathematics Subject Classification ID

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

Cites Work

• Kneser's conjecture, chromatic number, and homotopy
• A survey of the theory of hypercube graphs
• An update on the middle levels problem
• An explicit 1-factorization in the middle of the Boolean lattice
• Triangle-free Hamiltonian Kneser graphs
• The prism over the middle-levels graph is Hamiltonian
• A Survey of Combinatorial Gray Codes
• Title not available (Why is that?)
• An inductive construction for Hamilton cycles in Kneser graphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Updating the hamiltonian problem—A survey
• Hamiltonian uniform subset graphs
• Hamiltonian Kneser graphs
• Kneser graphs are Hamiltonian for \(n\geq 3k\)
• Monotone Gray codes and the middle levels problem
• Long cycles in the middle two layers of the discrete cube
• Gray codes with restricted density
• Lexicographic matchings cannot form Hamiltonian cycles
• Explicit matchings in the middle levels of the Boolean lattice
• Title not available (Why is that?)
• Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
• The antipodal layers problem
• On generalized middle-level problem
• Title not available (Why is that?)
• The Rugby footballers of Croam
• Title not available (Why is that?)

Cited In (17)

• Certain homological invariants of bipartite kneser graphs
• Some conditions implying stability of graphs
• Matching number, Hamiltonian graphs and magnetic Laplacian matrices
• Cayley properties of the line graphs induced by consecutive layers of the hypercube
• Sparse Kneser graphs are Hamiltonian
• Johnson graphs are panconnected
• Kneser graphs are Hamiltonian
• The automorphism group of the bipartite Kneser graph
• The toughness of Kneser graphs
• Graphs whose Kronecker covers are bipartite Kneser graphs
• The general position problem on Kneser graphs and on some graph operations
• Triangle-free Hamiltonian Kneser graphs
• REGULARITY OF POWERS OF BIPARTITE GRAPHS
• On 1-factorizations of bipartite Kneser graphs
• On the central levels problem
• A constant-time algorithm for middle levels Gray codes
• A short proof of the middle levels theorem

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

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