20.500.12556/DKUM-51909 On a local 3-Steiner convexity O lokalni 3-Steinerjevi konveksnosti Za dani graf ▫$G$▫ je Steinerjev interval množice vozlišč ▫$W subset V(G)$▫ množica tistih vozlišč, ki ležijo na kakem Steinerjevem drevesu glede na ▫$W$▫. Množica ▫$U subset V(G)$▫ je ▫$g_3$▫-konveksna v ▫$G$▫, če Steinerjev interval poljubne trojice vozlišč iz ▫$U$▫ v celoti leži v ▫$U$▫. Henning, Nielsen in Oellermann (2009) so dokazali, da graf ▫$G$▫, v katerem so ▫$j$▫-krogle ▫$g_3$▫-konveksne za vsak ▫$j ge 1$▫, ne vsebuje hiše niti grafov dvojčkov ▫$C_4$▫ kot induciranih podgrafov in vsak cikel v ▫$G$▫ dolžine vsaj šest je dobro premostljiv. V tem članku dokažemo, da velja tudi obrat tega izreka, s čimer okarakteriziramo grafe z ▫$g_3$▫-konveksnimi kroglami. Given a graph ▫$G$▫ and a set of vertices ▫$W subset V(G)$▫, the Steiner interval of ▫$W$▫ is the set of vertices that lie on some Steiner tree with respect to ▫$W$▫. A set ▫$W subset V(G)$▫ is called ▫$g_3$▫-convex in ▫$G$▫, if the Steiner interval with respect to any three vertices from ▫$U$▫ lies entirely in ▫$U$▫. Henning et al. (2009) proved that if every ▫$j$▫-ball for all ▫$j ge 1$▫ is ▫$g_3$▫-convex in a graph ▫$G$▫, then ▫$G$▫ has no induced house nor twin ▫$C_4$▫, and every cycle in ▫$G$▫ of length at least six is well-bridged. In this paper we show that the converse of this theorem is true, thus characterizing the graphs in which all balls are ▫$g_3$▫-convex. matematika teorija grafov Steinerjev interval razdalja dobra premostljivost mathematics graph theory Steiner interval distance well-bridgeness true false false Angleški jezik Angleški jezik Delo ni kategorizirano 2015-07-10 15:23:37 2015-07-10 15:23:37 2022-05-31 03:08:32 2019-07-11 07:31:44 2011 0 0 str. 1222-1235 no. 8 Vol. 32 2011 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 25427968 16079193 0195-6698 URN:SI:UM:DK:JORLTX3K http://dx.doi.org/10.1016/j.ejc.2011.06.001 1 https://dk.um.si/Dokument.php?lang=slv&id=76469 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0