| 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: | 1183 |
|---|
| Število prenosov: | 92 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
