20.500.12556/DKUM-52019 A characterization of the edge connectivity of direct products of graphs Karakterizacija povezanosti po povezavah direktnih produktov grafov V članku dokažemo formulo za povezanost po povezavah direktnega produkta grafov. V formuli se povezanost po povezavah produkta izraža kot funkcija povezanosti po povezavah, najmanjše stopnje, števila povezav in dvodelne frustracije obeh faktorjev. Prav tako v članku opišemo strukturo najmanjših presečnih množic v direktnih produktih grafov. The direct product of graphs ▫$G = (V(G),E(G))$▫ and ▫$H = (V(H),E(H))$▫ is the graph, denoted as ▫$G times H$▫, with vertex set ▫$V(G times H) = V(G) times V(H)$▫, where vertices ▫$(x_1,y_1)$▫ and ▫$(x_2,y_2)$▫ are adjacent in ▫$G times H$▫ if ▫$x_1x_2 in E(G)$▫ and ▫$y_1y_2 in E(H)$▫. The edge connectivity of a graph ▫$G$▫, denoted as ▫$lambda(G)$▫, is the size of a minimum edge-cut in ▫$G$▫. We introduce a function ▫$psi$▫ and prove the following formula ▫$$lambda (G times H) = min {2lambda(G)|E(H)|, 2lambda(H)|E(G)|, delta(G times H), psi(G,H), psi(H,G)} .$$▫ We also describe the structure of every minimum edge-cut in ▫$G times H$▫. matematika teorija grafov direktni produkt povezanost po povezavah mathematics graph theory direct product edge connectivity true false false Angleški jezik Angleški jezik Delo ni kategorizirano 2015-07-10 15:34:02 2015-07-10 15:34:02 2022-05-31 03:09:06 2019-07-11 07:34:59 2013 0 0 str. 1385-1393 iss. 12 Vol. 313 2013 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 16649305 0012-365X URN:SI:UM:DK:TBVG4KLW http://dx.doi.org/10.1016/j.disc.2013.02.011 1 https://dk.um.si/Dokument.php?lang=slv&id=76579 Fakulteta za strojništvo 0 0 0