Edge-connectivity of strong products of graphsBrešar, Boštjan (Avtor) Špacapan, Simon (Avtor) mathematicsgraph theoryconnectivitystrong productgraph productseparating setThe strong product ▫$G_1 \boxtimes G_2$▫ of graphs ▫$G_1$▫ and ▫$G_2$▫ is the graph with ▫$V(G_1) \times V(G_2)$▫ as the vertex set, and two distinct vertices ▫$(x_1,x_2)$▫ and ▫$(y_1,y_2)$▫ are adjacent whenever for each ▫$i\in \{1,2\}$▫ either ▫$x_i=y_i$▫ or ▫$x_iy_i \in E(G_i)$▫. In this note we show that for two connected graphs ▫$G_1$▫ and ▫$G_2$▫ the edge-connectivity ▫$\lambda(G_1 \boxtimes G_2)$▫ equals ▫$\min\{\delta(G_1\boxtimes G_2), \lambda(G_1)(|V(G_2)|+2|E(G_2)|), \lambda(G_2)(|V(G_1)|+2|E(G_1)|)\}$▫. In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.20072017-03-31 11:13:56Neznano65338ISSN: 1234-3099UDK: 519.17OceCobissID: 7487065COBISS_ID: 14368345ISSN pri članku: 1234-3099NUK URN: URN:SI:UM:DK:IXOITPK7sl