Connectivity of Strong Products of Graphs.

The strong product $${G\boxtimes H}$$ of graphs G = ( V1, E1) and H = ( V2, E2) is the graph with vertex set $${V(G \boxtimes H)=V_1\times V_2}$$, where two distinct vertices $${(x_1, x_2), (y_1, y_2)\in V_1\times V_2}$$ are adjacent in $${G\boxtimes H}$$ if and only if x i = y i or $${x_i y_i\in E_i}$$ for i = 1, 2. We introduce so called I-sets and L-sets in the strong product $${G\boxtimes H}$$ and prove that every minimum separating set in $${G\boxtimes H}$$ is either an I-set or an L-set in $${G\boxtimes H}$$. Some bounds and exact results for connectivity of strong products follow from this characterization. The result is then generalized to an arbitrary number of factors in the strong product. [ABSTRACT FROM AUTHOR]