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

At least 4 years old · documented by

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 n≥2k+1n\geq 2k+1, then the super-connectivity κ1\kappa_1 of KG(n,k)KG(n,k) is

κ1={2((n−kk)−1),2k+1≤n<3k,2((n−kk)−1)−(n−2kk),n≥3k.\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.

References

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.