Super connectivity of direct product of graphs - Zhou, Jin-Xin (Ars mathematica contemporanea, 2015)
For a graph ?$G$?, ?$κ(G)$? denotes its connectivity. A graph ?$G$? is super connected, or simply super-?$κ$?, if every minimum separating set is the neighborhood of a vertex of ?$G$?, that is, every minimum separating set isolates a vertex. The direct product ?$G_1 × G_2$? of two graphs ?$G_1$? and ?$G_2$? is a graph with vertex set ?$V(G_1 × G_2) = V(G_1) × V(G_2)$? and edge set ?$E(G_1 × G_2) = \{(u_1, v_1)(u_2, v_2) \vert u_1u_2 \in E(G1), v_1v_2 \in E(G2)\}$?. Let ?$Γ = G × K_n$?, where ?$G$? is a non-trivial graph and ?$K_n(n \ge 3)$? is a complete graph on ?$n$? vertices. In this paper, we show that ?$Γ$? is not super-?$κ$? if and only if either ?$κ(Γ) = nκ(G)$?, or ?$Γ \cong K_{\ell, \ell} × K_3(\ell > 0)$?.
Keywords: direct product; direktni produkt; super connectivity; super povezanost; vertex-cut; vozliščni rez