Czasopismo
Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
Warianty tytułu
Języki publikacji
Abstrakty
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
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
333-343
Opis fizyczny
Daty
wydano
2007
otrzymano
2006-05-04
poprawiono
2007-01-05
zaakceptowano
2007-01-05
Twórcy
autor
- University of Maribor, FEECS, Smetanova 17, 2000 Maribor, Slovenia
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1365