PDF

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

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

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