Discussiones Mathematicae Graph Theory 27(2) (2007) 333-343
doi: 10.7151/dmgt.1365

[BIBTex] [PDF] [PS]

EDGE-CONNECTIVITY OF STRONG PRODUCTS OF GRAPHS

Bostjan Bresar

University of Maribor, FEECS
Smetanova 17, 2000 Maribor, Slovenia
e-mail: bostjan.bresar@uni-mb.si

Simon Spacapan

University of Maribor, FME
Smetanova 17, 2000 Maribor, Slovenia
e-mail: simon.spacapan@uni-mb.si

Abstract

The strong product G1⊠ G2 of graphs G1 and G2 is the graph with V(G1)×V(G2) as the vertex set, and two distinct vertices (x1,x2) and (y1,y2) are adjacent whenever for each i ∈ {1,2} either xi = yi or xiyi ∈ E(Gi). In this note we show that for two connected graphs G1 and G2 the edge-connectivity λ (G1⊠G2) equals min{δ (G1⊠ G2),λ (G1)(|V(G2)|+2 |E(G2)|), λ(G2)(| V(G1)|+2| E(G1)|)}. 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.

2000 Mathematics Subject Classification: 05C40, 05C75.

References

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

Received 4 May 2006
Revised 5 January 2007
Accepted 5 January 2007