The Super-Connectivity of Kneser Graphs by Ekinci Gülnaz Boruzanli, Gauci John Baptist

“…The Kneser graph KG(n, k) is the graph whose vertices are the k-subsets of {1, 2, . . . , n} and two vertices are adjacent if the k-subsets are disjoint. We use Baranyai’s Theorem on the decompositions of complete hypergraphs to show that the Kneser graph KG are super-connected when n ≥ 5 and that their super-connectivity is n ( n/2) − 6 when n ≥ 6.…”
Get full text