Geodesic
Edge-connectivity of strong products of graphs
Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 2, pp. 333-343 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ 1,2 either x_i = y_i or x_i y_i ∈ E(G_i). In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals minδ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|). In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.
Keywords: connectivity, strong product, graph product, separating set 
@article{DMGT_2007_27_2_a9,
     author = {Bresar, Bostjan and Spacapan, Simon},
     title = {Edge-connectivity of strong products of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {333--343},
     year = {2007},
     volume = {27},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a9/}
}
TY  - JOUR
AU  - Bresar, Bostjan
AU  - Spacapan, Simon
TI  - Edge-connectivity of strong products of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2007
SP  - 333
EP  - 343
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a9/
LA  - en
ID  - DMGT_2007_27_2_a9
ER  - 
%0 Journal Article
%A Bresar, Bostjan
%A Spacapan, Simon
%T Edge-connectivity of strong products of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2007
%P 333-343
%V 27
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a9/
%G en
%F DMGT_2007_27_2_a9
Bresar, Bostjan; Spacapan, Simon. Edge-connectivity of strong products of graphs. Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 2, pp. 333-343. http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a9/

[1] W. Imrich and S. Klavžar, Product graphs: Structure and Recognition (John Wiley Sons, New York, 2000).

[2] S. Spacapan, Connectivity of Cartesian product of graphs, submitted 2005.

[3] S. Spacapan, Connectivity of strong products of graphs, submitted 2006.

[4] J.M. Xu and C. Yang, Connectivity of Cartesian product graphs, Discrete Math. 306 (2006) 159-165, doi: 10.1016/j.disc.2005.11.010.