Boruzanli and Gauci's super-connectivity conjecture for Kneser graphs

Let KG(n,k)KG(n,k) be the graph whose vertices are the kk-subsets of [n]={1,,n}[n]=\{1,\ldots,n\}, 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 κ1\kappa_1 is the size of a smallest nontrivial vertex cut, meaning one that does not isolate a single vertex. Boruzanli and Gauci's conjecture. If n2k+1n\geq 2k+1, then the super-connectivity κ1\kappa_1 of KG(n,k)KG(n,k) is

κ1={2((nkk)1),2k+1n<3k,2((nkk)1)(n2kk),n3k.\kappa_1=\begin{cases} 2\left({n-k \choose k}-1\right),&2k+1\leq n<3k,\\ 2\left({n-k \choose k}-1\right)-{n-2k\choose k},&n\geq 3k. \end{cases}

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.