PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2007 | 27 | 2 | 333-343
Tytuł artykułu

Edge-connectivity of strong products of graphs

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
27
Numer
2
Strony
333-343
Opis fizyczny
Daty
wydano
2007
otrzymano
2006-05-04
poprawiono
2007-01-05
zaakceptowano
2007-01-05
Twórcy
  • University of Maribor, FEECS, Smetanova 17, 2000 Maribor, Slovenia
  • 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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.