The super-connectivity of Kneser graphs
Makaleler > Tam Makale · 2018
Yazarlar: Gülnaz BORUZANLI EKİNCİ, John Baptist Gauci
Discussiones Mathematicae Graph Theory, SCI Expanded İndekslerine Giren Dergi, Uluslararası, Wos, 2018, cilt 39, ss 5-5
DOI: 10.7151/dmgt.2051
Özet
A vertex cut of a connected graph G is a set of vertices whose deletion disconnects G. A connected graph G is super-connected if the deletion of every minimum vertex cut of G isolates a vertex. The super-connectivity is the size of the smallest vertex cut of G such that each resultant component does not have an isolated vertex. 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(n, 2) are super-connected when n 5 and that their super-connectivity is n 2 -6 when n 6.