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.
Keywords: Connectivity, super-connectivity, odd graph, Kneser graph, bipartite Kneser graph, Kronecker double cover
@article{RO_2021__55_S1_S699_0,
author = {Boruzanl{\i} Ek\ensuremath{\dot{}}in\.{c}i, G\"ulnaz and Gauci, John Baptist},
title = {The super-connectivity of odd graphs and of their kronecker double cover},
journal = {RAIRO. Operations Research},
pages = {S699--S704},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020004},
mrnumber = {4223103},
zbl = {1469.05094},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020004/}
}
TY - JOUR AU - Boruzanlı Ek̇inċi, Gülnaz AU - Gauci, John Baptist TI - The super-connectivity of odd graphs and of their kronecker double cover JO - RAIRO. Operations Research PY - 2021 SP - S699 EP - S704 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020004/ DO - 10.1051/ro/2020004 LA - en ID - RO_2021__55_S1_S699_0 ER -
%0 Journal Article %A Boruzanlı Ek̇inċi, Gülnaz %A Gauci, John Baptist %T The super-connectivity of odd graphs and of their kronecker double cover %J RAIRO. Operations Research %D 2021 %P S699-S704 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020004/ %R 10.1051/ro/2020004 %G en %F RO_2021__55_S1_S699_0
Boruzanlı Ek̇inċi, Gülnaz; Gauci, John Baptist. The super-connectivity of odd graphs and of their kronecker double cover. RAIRO. Operations Research, Tome 55 (2021), pp. S699-S704. doi: 10.1051/ro/2020004
and , The -restricted edge-connectivity of Kneser graphs. Appl. Math. Comput. 343 (2019) 258–267. | MR | Zbl
, Synthesis of reliable networks – a survey. IEEE Trans. Reliab. 35 (1986) 240–246. | Zbl | DOI
and , Circulants and their connectivities. J. Graph Theory 8 (1984) 487–499. | MR | Zbl | DOI
and , On the reliability of generalized Petersen graphs. Discrete Appl. Math. 252 (2019) 2–9. | MR | Zbl | DOI
and , The super-connectivity of Johnson graphs. Discrete Math. Theor. Comput. Sci. 22 (2020) 12. | MR | Zbl
and , The super-connectivity of Kneser graphs. Discuss. Math. Graph Theory 39 (2019) 5–11. | MR | Zbl | DOI
and , Super connectivity of Kronecker product of complete bipartite graphs and complete graphs. Discrete Math. 339 (2016) 1950–195. | MR | Zbl | DOI
and , Super edge connectivity of Kronecker products of graphs. Int. J. Found. Comput. Sci. 25 (2014) 59–65. | MR | Zbl | DOI
and , Hamiltonian uniform subset graphs. J. Comb. Theory, Ser. B. 42 (1987) 257–263. | MR | Zbl | DOI
, and , On middle cube graphs. Electron. J. Graph Theory App. 3 (2015) 133–145. | MR | Zbl
and , Kronecker covers, -construction, unit-distance graphs and isometric point-circle configurations. Ars Math. Contemp. 7 (2013). | MR | Zbl | DOI
and , Super connectivity of Kronecker products of some graphs. Ars Comb. 123 (2015) 65–73. | MR | Zbl
, , and , Fault tolerance of locally twisted cubes. Appl. Math. Comput. 334 (2018) 401–406. | MR | Zbl
, Conditional connectivity. Networks 13 (1983) 347–357. | MR | Zbl | DOI
, Cayley graphs and interconnection networks, edited by and . In: Graph Symmetry: Algebraic Methods and Applications. Springer Netherlands, Dordrecht (1997) 167–224. | MR | Zbl | DOI
, , and , Embedding hypercubes, rings, and odd graphs into hyper-stars. Int. J. Comput. Math. 86 (2009) 771–778. | MR | Zbl | DOI
, WR Hamilton’s Dodekaederaufgabe als Buntordnungproblem. Sitzungsber. Akad. Wiss. Wien (Abt. IIa) 126 (1917) 67–90, 963–1007. | JFM
, Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory Ser. A. 25 (1978) 319–324. | MR | Zbl | DOI
, , and , On super connectivity of Cartesian product graphs. Networks 52 (2008) 78–87. | MR | Zbl | DOI
, On the automorphism groups of regular hyperstars and folded hyperstars. Ars Comb. 123 (2011) 75–86. | MR | Zbl
and , Some algebraic properties of bipartite Kneser graphs. Preprint arXiv:1804.04570, to appear in Ars Combinatoria (2018). | MR | Zbl
and , Bipartite Kneser graphs are Hamiltonian. Electron. Notes Discrete Math. 49 (2015) 259–267. | Zbl | DOI
, Connectivity of transitive graphs. J. Comb. Theory 8 (1970) 23–29. | MR | Zbl | DOI
and , Extraconnectivity of hypercubes. Appl. Math. Lett. 22 (2009) 887–891. | MR | Zbl | DOI
and , Extraconnectivity of hypercubes (II). Australas. J. Comb. 47 (2010) 189–195. | MR | Zbl
Cité par Sources :
