A note on Steiner intervals and betweenness

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

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	A note on Steiner intervals and betweenness
Avtorji:	ID Changat, Manoj (Avtor) ID Lakshmikuttyamma, Anandavally K. (Avtor) ID Mathews, Joseph (Avtor) ID Peterin, Iztok (Avtor) ID Narasimha-Shenoi, Prasanth G. (Avtor) ID Tepeh, Aleksandra (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.disc.2011.08.009
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
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
PID:	20.500.12556/DKUM-51908
UDK:	519.17
COBISS.SI-ID:	16078937
ISSN pri članku:	0012-365X
NUK URN:	URN:SI:UM:DK:SNZ0S68F
Datum objave v DKUM:	10.07.2015
Število ogledov:	1032
Število prenosov:	87
Metapodatki:
Področja:	Ostalo
:	CHANGAT, Manoj, LAKSHMIKUTTYAMMA, Anandavally K., MATHEWS, Joseph, PETERIN, Iztok, NARASIMHA-SHENOI, Prasanth G. in TEPEH, Aleksandra, 2011, A note on Steiner intervals and betweenness. Discrete mathematics [na spletu]. 2011. Vol. 311, no. 22, p. 2601–2609. [Dostopano 1 april 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2011.08.009 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

Ni podobnih del

Podobna dela iz ostalih repozitorijev:

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

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