# Edge-connectivity of strong products of graphs

Bostjan Bresar; Simon Spacapan

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 2, page 333-343
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBostjan Bresar, and Simon Spacapan. "Edge-connectivity of strong products of graphs." Discussiones Mathematicae Graph Theory 27.2 (2007): 333-343. <http://eudml.org/doc/270713>.

@article{BostjanBresar2007,

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 ∈ 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.},

author = {Bostjan Bresar, Simon Spacapan},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {connectivity; strong product; graph product; separating set; separating sets},

language = {eng},

number = {2},

pages = {333-343},

title = {Edge-connectivity of strong products of graphs},

url = {http://eudml.org/doc/270713},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Bostjan Bresar

AU - Simon Spacapan

TI - Edge-connectivity of strong products of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 2

SP - 333

EP - 343

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

LA - eng

KW - connectivity; strong product; graph product; separating set; separating sets

UR - http://eudml.org/doc/270713

ER -

## References

top- [1] W. Imrich and S. Klavžar, Product graphs: Structure and Recognition (John Wiley & Sons, New York, 2000). Zbl0963.05002
- [2] S. Spacapan, Connectivity of Cartesian product of graphs, submitted 2005. Zbl1152.05340
- [3] S. Spacapan, Connectivity of strong products of graphs, submitted 2006. Zbl1213.05154
- [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. Zbl1085.05042

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.