The super-connectivity of Kneser graphs
| Autor: | Gülnaz Boruzanlı Ekinci, John Baptist Gauci |
|---|---|
| Přispěvatelé: | Ege Üniversitesi |
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 39, Iss 1, Pp 5-11 (2019) |
| ISSN: | 2083-5892 1234-3099 |
| DOI: | 10.7151/dmgt.2051 |
| Popis: | WOS: 000454521100001 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|