Edge-connectivity of strong products of graphs

• Autorzy: Bostjan Bresar , Simon Spacapan
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

connectivity; strong product; graph product; separating set

Kategorie tematyczne

• 05C75: Structural characterization of families of graphs
• 05C40: Connectivity

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 2
• Strony: 333-343

Daty

wydano

2007

otrzymano

2006-05-04

poprawiono

2007-01-05

zaakceptowano

2007-01-05

Twórcy

autor

Bostjan Bresar

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

autor

Simon Spacapan

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1365