Boruzanli and Gauci's super-connectivity conjecture for Kneser graphs
Boruzanli and Gauci's super-connectivity conjecture for Kneser graphs
Let be the graph whose vertices are the -subsets of , with two vertices adjacent exactly when the corresponding subsets are disjoint. A vertex cut is a set of vertices whose deletion disconnects the graph; the super-connectivity is the size of a smallest nontrivial vertex cut, meaning one that does not isolate a single vertex. Boruzanli and Gauci's conjecture. If , then the super-connectivity of is
The conjecture gives the expected minimum nontrivial vertex-cut size for Kneser graphs, refining the known connectivity result. The supplied source does not state whether it has been proved or disproved, so its status remains open.
Sources & referencesView supporting material
Primary source
Yulan Chen, Yuqing Lin and Weigen Yan, “The super-connectivity of Kneser graph KG(n,3)”, arXiv:2103.10041 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.