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 or . 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1365,
author = {Bostjan Bresar and Simon Spacapan},
title = {Edge-connectivity of strong products of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {27},
year = {2007},
pages = {333-343},
zbl = {1135.05034},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1365}
}
Bostjan Bresar; Simon Spacapan. Edge-connectivity of strong products of graphs. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 333-343. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1365/
[000] [1] W. Imrich and S. Klavžar, Product graphs: Structure and Recognition (John Wiley & Sons, New York, 2000). | Zbl 0963.05002
[001] [2] S. Spacapan, Connectivity of Cartesian product of graphs, submitted 2005. | Zbl 1152.05340
[002] [3] S. Spacapan, Connectivity of strong products of graphs, submitted 2006. | Zbl 1213.05154
[003] [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. | Zbl 1085.05042