Bipartite Kneser graphs are Hamiltonian (Q5895045)
From MaRDI portal
scientific article; zbMATH DE number 6909484
Language | Label | Description | Also known as |
---|---|---|---|
English | Bipartite Kneser graphs are Hamiltonian |
scientific article; zbMATH DE number 6909484 |
Statements
Bipartite Kneser graphs are Hamiltonian (English)
0 references
23 July 2018
0 references
The article under review considers the bipartite Kneser graph \(H(n,k)\) whose vertices are the \(k\) element and \(n-k\) element subsets of a ground set \([n]=\{1,2,\ldots n\}\) and an edge between any two vertices if and only if one of the corresponding sets is a subset of the other. In the paper, it is proved that \(H(n,k)\) is Hamiltonian. Further some new results are proved about long cycles in the Kneser graph \(K(2k+o(k),k)\) whose vertices are \(k\)-element subsets of \([n]\), two such being adjacent if and only if the corresponding sets are disjoint. These main results follow from a technical lemma about cycles and paths in the hypercube.
0 references
Kneser graph
0 references
bipartite Kneser graph
0 references
Hamiltonian cycle
0 references
hypercube
0 references