20.500.12556/DKUM-51908 A note on Steiner intervals and betweenness Notica o 3-Steinerjevih intervalih in vmesnost Geodetka in geodetski interval, ki je sestavljen iz vseh vozlišč, ki pripadajo kakšni geodetki med fiksnim parom vozlišč v povezanem grafu ▫$G$▫, sta sestavni del metrične teorije grafov. Prav tako je znano, da je Steinerjevo drevo (multi) množice s ▫$k$▫ (▫$k>2$▫) vozlišči, posplošitev geodetke. V (B. Brešar, M. Changat, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114--6125) so se avtorji ukvarjali s ▫$k$▫-Steinerjevimi intervali ▫$S(u_{1},u_{2},ldots, u_{k})$▫ povezanih grafov (▫$k geq 3$▫) kot ▫$k$▫-arnimi posplošitvami geodetskih intervalov. Analogno sta bila iz binarne na ▫$k$▫-arno funkcijo posplošena tudi vmesnostni aksiom (b2) in monotoni aksiom(m) kot: za vsa vozlišča ▫$u_{1}, ldots, u_{k}, x, x_{1}, ldots, x_{k} in V(G)$▫, ki niso nujno različna ▫$$(b2)quad x in S(u_{1}, u_{2}, ldots, u_{k}) Rightarrow S(x, u_{2}, ldots, u_{k}) subseteq S(u_{1}, u_{2}, ldots, u_{k}),$$▫ ▫$$(m) quad x_{1}, ldots, x_{k} in S(u_{1}, ldots, u_{k})Rightarrow S(x_{1}, ldots,x_{k}) subseteq S(u_{1}, ldots, u_{k}).$$▫ Avtorji so v zgoraj omenjenem članku domnevali, da ▫$3$▫-Steinerjev interval povezanega grafa ▫$G$▫ zadošča vmesnostnemu aksiomu (b2) natanko tedaj, ko je vsak blok grafa ▫$G$▫ geodetski z diametrom največ 2. V tem delu dokažemo to domnevo. Pri tem dodatno dokažemo, da v vsakem geodetskem bloku z diametrom vsaj 3 obstaja izometrični cikel dolžine ▫$2k+1$▫, ▫$k>2$▫. Prav tako predstavimo dodaten aksiom (b2(2)), ki je smiseln le za 3-Steinerjeve intervale in pokažemo, da je le ta ekvivalenten monotonemu aksiomu. The geodesic and geodesic interval, namely the set of all vertices lying on geodesics between a pair of vertices in a connected graph, is a part of folklore in metric graph theory. It is also known that Steiner tree of a (multi) set with ▫$k$▫ (▫$k>2$▫) vertices, generalizes geodesics. In (B. Brešar, M. Changat, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114-6125) the authors studied the ▫$k$▫-Steiner intervals ▫$S(u_{1}, u_{2}, ldots, u_{k})$▫ on connected graphs (▫$k geq 3$▫) asthe ▫$k$▫-ary generalization of the geodesic intervals. The analogous betweenness axiom (b2) and the monotone axiom (m) were generalized from binary to ▫$k$▫-ary functions as: for any ▫$u_{1}, ldots, u_{k}, x, x_{1}, ldots, x_{k} in V(G)$▫ which are not necessarily distinct, ▫$$(b2) quad x in S(u_{1}, u_{2}, ldots, u_{k}) Rightarrow S(x,u_{2}, ldots, u_{k}) subseteq S(u_{1}, u_{2}, ldots, u_{k}),$$▫ ▫$$(m) quad x_{1}, ldots, x_{k} in S(u_{1}, ldots, u_{k}) Rightarrow S(x_{1}, ldots, x_{k}) subseteq S(u_{1}, ldots, u_{k}). ▫$$ The authors conjectured that the ▫$3$▫-Steiner interval on a connected graph ▫$G$▫ satisfies the betweenness axiom (b2) if and only if each block of ▫$G$▫ is geodetic of diameter at most 2. In this paper we settle this conjecture. For this we show that there exists an isometric cycle of length ▫$2k+1$▫, ▫$k>2$▫, in every geodetic block of diameter at least 3. We also introduce another axiom (b2(2)), which is meaningful only to ▫$3$▫-Steiner intervals and show that this axiom is equivalent to the monotone axiom. matematika teorija grafov Steinerjev interval geodetski graf vmesnost mathematics graph theory Steiner interval geodetic graph betweenness true false false Angleški jezik Angleški jezik Delo ni kategorizirano 2015-07-10 15:23:35 2015-07-10 15:23:35 2022-05-31 03:08:32 2019-07-11 07:31:42 2011 0 0 Str. 2601-2609 iss. 22 Vol. 311 2011 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 16078937 0012-365X URN:SI:UM:DK:SNZ0S68F http://dx.doi.org/10.1016/j.disc.2011.08.009 1 https://dk.um.si/Dokument.php?lang=slv&id=76468 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0