The Library
Bipartite Kneser graphs are Hamiltonian
Tools
Tools
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
|
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 > 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 | ||||||||
| Publisher Statement: | 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 | ||||||||
| 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
