| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:A note on Steiner intervals and betweenness
Avtorji:Changat, Manoj (Avtor)
Lakshmikuttyamma, Anandavally K. (Avtor)
Mathews, Joseph (Avtor)
Peterin, Iztok (Avtor)
Narasimha-Shenoi, Prasanth G. (Avtor)
Tepeh, Aleksandra (Avtor)
Datoteke:URL http://dx.doi.org/10.1016/j.disc.2011.08.009
 
Jezik:Angleški jezik
Vrsta gradiva:Delo ni kategorizirano (r6)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Opis: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
Leto izida:2011
Št. strani:Str. 2601-2609
Številčenje:Vol. 311, iss. 22
UDK:519.17
COBISS_ID:16078937 Povezava se odpre v novem oknu
ISSN pri članku:0012-365X
NUK URN:URN:SI:UM:DK:SNZ0S68F
Število ogledov:379
Število prenosov:47
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Discrete Mathematics
Skrajšan naslov:Discrete math.
Založnik:North-Holland
ISSN:0012-365X
COBISS.SI-ID:1118479 Novo okno

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Notica o 3-Steinerjevih intervalih in vmesnost
Opis: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.


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici