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)$?.

Pravice

URN

URN:NBN:SI:DOC-5JWYIMXY

COBISSID

17372505

Objavljeno

29.05.2020

Metapodatki

Citiranje

APA:

Zhou, Jin-Xin (2015). Super connectivity of direct product of graphs. Ars mathematica contemporanea, letnik 8, številka 2, str. 235-244. URN:NBN:SI:DOC-5JWYIMXY from http://www.dlib.si

MLA:

Zhou, Jin-Xin. "Super connectivity of direct product of graphs." Ars mathematica contemporanea letnik 8. številka 2 (2015) str. 235-244.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-5JWYIMXY>

Ars mathematica contemporanea
2008-
(Zbirni zapis)