The super edge connectivity of Kronecker product graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 561-566.

Let G 1 and G 2 be two graphs. The Kronecker product G 1 × G 2 has vertex set V ( G 1 × G 2 ) = V ( G 1 ) × V ( G 2 ) and edge set E ( G 1 × G 2 ) = { ( u 1 , v 1 ) ( u 2 , v 2 ) : u 1 u 2 E ( G 1 ) and v 1 v 2 E ( G 2 ) } . In this paper we determine the super edge–connectivity of G × K n for n 3 . More precisely, for n 3 , if λ ' ( G ) denotes the super edge–connectivity of G , then at least  min { n ( n - 1 ) λ ' ( G ) , min x y E ( G ) { deg G ( x ) + deg G ( y ) } ( n - 1 ) - 2 } edges need to be removed from G × K n to get a disconnected graph that contains no isolated vertices.

DOI : 10.1051/ro/2017080
Classification : 05C40, 68M10, 68R10
Mots-clés : Connectivity, Super connectivity, super edge connectivity, Kronecker product, fault tolerance
Boruzanli Ekinci, Gülnaz 1 ; Kirlangic, Alpay 1

1
@article{RO_2018__52_2_561_0,
     author = {Boruzanli Ekinci, G\"ulnaz and Kirlangic, Alpay},
     title = {The super edge connectivity of {Kronecker} product graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {561--566},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {2},
     year = {2018},
     doi = {10.1051/ro/2017080},
     mrnumber = {3880544},
     zbl = {1398.05172},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2017080/}
}
TY  - JOUR
AU  - Boruzanli Ekinci, Gülnaz
AU  - Kirlangic, Alpay
TI  - The super edge connectivity of Kronecker product graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 561
EP  - 566
VL  - 52
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2017080/
DO  - 10.1051/ro/2017080
LA  - en
ID  - RO_2018__52_2_561_0
ER  - 
%0 Journal Article
%A Boruzanli Ekinci, Gülnaz
%A Kirlangic, Alpay
%T The super edge connectivity of Kronecker product graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 561-566
%V 52
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2017080/
%R 10.1051/ro/2017080
%G en
%F RO_2018__52_2_561_0
Boruzanli Ekinci, Gülnaz; Kirlangic, Alpay. The super edge connectivity of Kronecker product graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 561-566. doi : 10.1051/ro/2017080. http://www.numdam.org/articles/10.1051/ro/2017080/

[1] N. Alon and E. Lubetzky, Independent sets in tensor graph powers. J. Graph Theory 54 (2007) 73–87 | DOI | MR | Zbl

[2] G. Boruzanli Ekinci and A. Kirlangiç, The super connectivity of kronecker productgraphs 2016 | Numdam | MR | Zbl

[3] G. Boruzanli Ekinci and A. Kirlangiç, Super connectivity of kronecker product of complete bipartite graphs and complete graphs. Discrete Math. 339 (2016) 1950–1953 | DOI | MR | Zbl

[4] B. Bresar, W. Imrich, S. Klavzar and B. Zmazek, Hypercubes as direct products. SIAM J. Discrete Math. 18 (2005) 778–786 | DOI | MR | Zbl

[5] B. Brešar and S. Špacapan, On the connectivity of the direct product of graphs. Austral. J. Combin. 41 (2008) 45–56 | MR | Zbl

[6] X.L. Cao, Š. Brglez, S. Špacapan and E. Vumar, On edge connectivity of direct products of graphs. Inf. Proc. Lett. 111 (2011) 899–902 | DOI | MR | Zbl

[7] X.L. Cao and E. Vumar, Super edge connectivity of kronecker products of graphs. Inter. J. Found. Comput. Sci. 25 (2014) 59–65 | DOI | MR | Zbl

[8] G. Dirac, Généralisations du théoréme de menger. C. R. Acad. Sci. 250 (1960) 4252–4253 | MR | Zbl

[9] A.-H. Esfahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph. Inf. Proc. Lett. 27 (1988) 195–199 | DOI | MR | Zbl

[10] M. Angel Fiol, J. Fabrega and M. Escudero, Short paths and connectivity in graphs and digraphs. Ars Combinatoria 29 (1990) 17–31 | MR | Zbl

[11] S.A. Ghozati, A finite automata approach to modeling the cross product of interconnection networks. Math. Comput. Model. 30 (1999) 185–200 | DOI | MR | Zbl

[12] F. Harary, Conditional connectivity. Networks 13 (1983) 347–357 | DOI | MR | Zbl

[13] R.H. Lamprey and B.H. Barnes, Products of graphs and applications. Model. Simul. 5 (1974) 1119–1123 | MR

[14] J. Leskovec, D. Chakrabarti, J. Kleinberg, Ch. Faloutsos and Z. Ghahramani, Kronecker graphs: An approach to modeling networks.J. Machine Learn. Res. 11 (2010) 985–1042 | MR | Zbl

[15] D.J. Miller, The categorical product of graphs. Canadian J. Math. 20 (1968) 1511–1521 | DOI | MR | Zbl

[16] J. Nešetřil, Representations of graphs by means of products and their complexity. In Math. Found. Comput. Sci. Springer (1981) 94–102 | MR | Zbl

[17] H. Wang, E. Shan and W. Wang, On the super connectivity of Kronecker products of graphs. Inf. Proc. Lett. 112 (2012) 402–405 | DOI | MR | Zbl

[18] W. Wang and N.N. Xue, Connectivity of direct products of graphs. Ars Combinatoria 100 (2011) 107–111 | MR | Zbl

[19] Y. Wang and B. Wu, Proof of a conjecture on connectivity of kronecker product of graphs. Discrete Math. 311 (2011) 2563–2565. | DOI | MR | Zbl

[20] P.M. Weichsel, The kronecker product of graphs. Proc. Amer. Math. Soc. 13 (1962) 47–52 | DOI | MR | Zbl

[21] D. Brentwest, Introduction to graph theory, volume 2. Prentice hall Upper Saddle River (2001) | Zbl

[22] J.-X. Zhou, Super connectivity of direct product of graphs. Ars Math. Contemporanea 8 (2015) 235–244 | DOI | MR | Zbl

Cité par Sources :