Edge-connectivity of strong products of graphs

Bostjan Bresar; Simon Spacapan

ArticleOriginal scientific text

Title

Edge-connectivity of strong products of graphs

Authors ¹, ²

Affiliations

University of Maribor, FEECS, Smetanova 17, 2000 Maribor, Slovenia
University of Maribor, FME, Smetanova 17, 2000 Maribor, Slovenia

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_{i} y_{i} \in 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

ENG

connectivity, strong product, graph product, separating set

W. Imrich and S. Klavžar, Product graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
S. Spacapan, Connectivity of Cartesian product of graphs, submitted 2005.
S. Spacapan, Connectivity of strong products of graphs, submitted 2006.
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.

Title

Edge-connectivity of strong products of graphs

Affiliations

Abstract

Keywords

Bibliography