The super-connectivity of odd graphs and of their kronecker double cover
| Autor: | Gülnaz Boruzanlı Ekinci, John Baptist Gauci |
|---|---|
| Přispěvatelé: | Ege Üniversitesi |
| Rok vydání: | 2021 |
| Předmět: |
bipartite Kneser graph
0102 computer and information sciences 02 engineering and technology Disjoint sets Management Science and Operations Research 01 natural sciences Theoretical Computer Science Combinatorics symbols.namesake Kronecker delta 0202 electrical engineering electronic engineering information engineering Mathematics Kronecker product Connectivity Double cover super-connectivity Kneser graph Complete graph 020206 networking & telecommunications Kronecker double cover Computer Science Applications odd graph 010201 computation theory & mathematics symbols Odd graph Bipartite graph |
| Zdroj: | RAIRO - Operations Research. 55:S699-S704 |
| ISSN: | 1290-3868 0399-0559 |
| DOI: | 10.1051/ro/2020004 |
| Popis: | The study of connectivity parameters forms an integral part of the research conducted in establishing the fault tolerance of networks. A number of variations on the classical notion of connectivity have been proposed and studied. In particular, the super-connectivity asks for the minimum number of vertices that need to be deleted from a graph in order to disconnect the graph without creating isolated vertices. In this work, we determine this value for two closely related families of graphs which are considered as good models for networks, namely the odd graphs and their Kronecker double cover. The odd graphs are constructed by taking all possible subsets of size k from the set of integers {1,…,2k + 1} as vertices, and defining two vertices to be adjacent if the corresponding k-subsets are disjoint; these correspond to the Kneser graphs KG(2k + 1, k). The Kronecker double cover of a graph G is formed by taking the Kronecker product of G with the complete graph on two vertices; in the case when G is KG(2k + 1, k), the Kronecker double cover is the bipartite Kneser graph H(2k + 1, k). We show that in both instances, the super-connectivity is equal to 2k. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|