The Library
Bipartite Kneser graphs are Hamiltonian
Tools
Mutze, Torsten and Su, Pascal (2017) Bipartite Kneser graphs are Hamiltonian. Combinatorica, 37 (6). pp. 1207-1219. doi:10.1007/s00493-016-3434-6 ISSN 0209-9683.
|
PDF
WRAP-bipartite-Kneser-graphs-Hamiltonian-Mutze-2016.pdf - Accepted Version - Requires a PDF viewer. Download (733Kb) | Preview |
Official URL: https://doi.org/10.1007/s00493-016-3434-6
Abstract
For integers $k\geq 1$ and $n\geq 2k+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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Hypercube, Hamiltonian graph theory, Bipartite graphs | ||||||||
Journal or Publication Title: | Combinatorica | ||||||||
Publisher: | Springer | ||||||||
ISSN: | 0209-9683 | ||||||||
Official Date: | December 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 37 | ||||||||
Number: | 6 | ||||||||
Page Range: | pp. 1207-1219 | ||||||||
DOI: | 10.1007/s00493-016-3434-6 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Reuse Statement (publisher, data, author rights): | This is a post-peer-review, pre-copyedit version of an article published in Combinatorica. The final authenticated version is available online at: https://doi.org/10.1007/s00493-016-3434-6 | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 17 June 2019 | ||||||||
Date of first compliant Open Access: | 25 June 2019 | ||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year