Super connectivity of direct product of graphs - Zhou, Jin-Xin (Ars mathematica contemporanea, 2015)
Za graf ?$G$? naj ?$κ(G)$? označuje njeno povezanost. Graf ?$G$? je super povezan, ali na kratko super-?$κ$?, če je vsaka minimalna separirajoča množica okolica vozlišča iz ?$G$?, to pomeni, da vsaka minimalna separirajoča množica izolira neko vozlišče. Direktni produkt ?$G_1 × G_2$? grafov ?$G_1$? in ?$G_2$? je graf z množico vozlišč ?$V(G_1 × G_2) = V(G_1) × V(G_2)$? in množico povezav ?$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)\}$?. Naj bo ?$Γ = G × K_n$?, kjer je ?$G$? netrivialen graf in ?$K_n(n \ge 3)$? poln graf na ?$n$? vozliščih. V tem članku pokažemo, da ?$Γ$? ni super-?$κ$?, če in samo če je bodisi ?$κ(Γ) = nκ(G)$? bodisi je ?$Γ \cong K_{\ell, \ell} × K_3(\ell > 0)$?.
Keywords: direct product; direktni produkt; super connectivity; super povezanost; vertex-cut; vozliščni rez