The super edge connectivity of Kronecker product graphs

Boruzanli Ekinci, Gülnaz; Kirlangic, Alpay

doi:10.1051/ro/2017080

Geodesic

Parcourir par

The super edge connectivity of Kronecker product graphs

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

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

Voir la notice de l'article provenant de la source Numdam

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

DOI : 10.1051/ro/2017080

Classification : 05C40, 68M10, 68R10
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :