410 KB22 KB200820252015Zhou, Jin-Xinštevilka:2letnik:8str. 235-244COBISSID:17372505ISSN:1855-3966URN:URN:NBN:SI:doc-5JWYIMXYenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneadirect productdirektni produktsuper connectivitysuper povezanostvertex-cutvozliščni rezSuper connectivity of direct product of graphs|For a graph ?$G$?, ?$\kappa(G)$? denotes its connectivity. A graph ?$G$? is super connected, or simply super-?$\kappa$?, 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 \times G_2$? of two graphs ?$G_1$? and ?$G_2$? is a graph with vertex set ?$V(G_1 \times G_2) = V(G_1) \times V(G_2)$? and edge set ?$E(G_1 \times G_2) = \{(u_1, v_1)(u_2, v_2) \vert u_1u_2 \in E(G1), v_1v_2 \in E(G2)\}$?. Let ?$\Gamma = G \times 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 ?$\Gamma$? is not super-?$\kappa$? if and only if either ?$\kappa(\Gamma) = n\kappa(G)$?, or ?$\Gamma \cong K_{\ell, \ell} \times K_3(\ell > 0)$?Za graf ?$G$? naj ?$\kappa(G)$? označuje njeno povezanost. Graf ?$G$? je super povezan, ali na kratko super-?$\kappa$?, č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 \times G_2$? grafov ?$G_1$? in ?$G_2$? je graf z množico vozlišč ?$V(G_1 \times G_2) = V(G_1) \times V(G_2)$? in množico povezav ?$E(G_1 \times 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 ?$\Gamma = G \times 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 ?$\Gamma$? ni super-?$\kappa$?, če in samo če je bodisi ?$\kappa(\Gamma) = n\kappa(G)$? bodisi je ?$\Gamma \cong K_{\ell, \ell} \times K_3(\ell > 0)$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije