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

Abstract

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

How to cite

top

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

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.