The super edge connectivity of Kronecker product graphs

Boruzanli Ekinci, Gülnaz; Kirlangic, Alpay

doi:10.1051/ro/2017080

Boruzanli Ekinci, Gülnaz ¹ ; Kirlangic, Alpay ¹

RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 561-566.

Résumé

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

MR Zbl | 1 citation dans Numdam

DOI : 10.1051/ro/2017080

Classification : 05C40, 68M10, 68R10
Mots clés : Connectivity, Super connectivity, super edge connectivity, Kronecker product, fault tolerance

Affiliations des auteurs :

Boruzanli Ekinci, Gülnaz ¹ ; Kirlangic, Alpay ¹

@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/

Bibliographie
Cité par

[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 :