Manoj Changat (Avtor), Anandavally K. Lakshmikuttyamma (Avtor), Joseph Mathews (Avtor), Iztok Peterin (Avtor), Prasanth G. Narasimha-Shenoi (Avtor), Aleksandra Tepeh (Avtor)

Povzetek

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.

Ključne besede

matematika;teorija grafov;Steinerjev interval;geodetski graf;vmesnost;mathematics;graph theory;Steiner interval;geodetic graph;betweenness;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK: 519.17
COBISS: 16078937 Povezava se bo odprla v novem oknu
ISSN: 0012-365X
Št. ogledov: 47
Št. prenosov: 30
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Notica o 3-Steinerjevih intervalih in vmesnost
Sekundarni povzetek: 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.
Sekundarne ključne besede: matematika;teorija grafov;Steinerjev interval;geodetski graf;vmesnost;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: Str. 2601-2609
Letnik: Vol. 311
Zvezek: iss. 22
Čas izdaje: 2011
ID: 1475889