- Tytuł:
- The Super-Connectivity of Kneser Graphs
- Autorzy:
-
Ekinci, Gülnaz Boruzanli
Gauci, John Baptist - Powiązania:
- https://bibliotekanauki.pl/articles/31343789.pdf
- Data publikacji:
- 2019-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
connectivity
super-connectivity
Kneser graphs - Opis:
- 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$ are super-connected when $n \ge 5$ and that their super-connectivity is \( \binom{n}{2} − 6 \) when $ n \ge 6 $.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 5-11
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł