Edge-connectivity of strong products of graphs | Zendy

Boštjan Brešar | Zendy; Simon Špacapan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Edge-connectivity of strong products of graphs

Author(s) -

Boštjan Brešar,

Simon Špacapan

Publication year - 2007

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1365

Subject(s) - mathematics , combinatorics , enhanced data rates for gsm evolution , computer science , artificial intelligence

The strong product G1 £G2 of graphs G1 and G2 is the graph with V (G1) × V (G2) as the vertex set, and two distinct vertices (x1, x2) and (y1, y2) are adjacent whenever for each i ∈ {1, 2} either xi = yi or xiyi ∈ E(Gi). In this note we show that for two connected graphs G1 and G2 the edge-connectivity λ(G1£G2) equals min{δ(G1£ G2), λ(G1)(|V (G2)|+2|E(G2)|), λ(G2)(|V (G1)|+2|E(G1)|)}. In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research