| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:On a local 3-Steiner convexity
Avtorji:Brešar, Boštjan (Avtor)
Gologranc, Tanja (Avtor)
Datoteke:URL http://dx.doi.org/10.1016/j.ejc.2011.06.001
 
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:Za dani graf ▫$G$▫ je Steinerjev interval množice vozlišč ▫$W subset V(G)$▫ množica tistih vozlišč, ki ležijo na kakem Steinerjevem drevesu glede na ▫$W$▫. Množica ▫$U subset V(G)$▫ je ▫$g_3$▫-konveksna v ▫$G$▫, če Steinerjev interval poljubne trojice vozlišč iz ▫$U$▫ v celoti leži v ▫$U$▫. Henning, Nielsen in Oellermann (2009) so dokazali, da graf ▫$G$▫, v katerem so ▫$j$▫-krogle ▫$g_3$▫-konveksne za vsak ▫$j ge 1$▫, ne vsebuje hiše niti grafov dvojčkov ▫$C_4$▫ kot induciranih podgrafov in vsak cikel v ▫$G$▫ dolžine vsaj šest je dobro premostljiv. V tem članku dokažemo, da velja tudi obrat tega izreka, s čimer okarakteriziramo grafe z ▫$g_3$▫-konveksnimi kroglami.
Ključne besede:matematika, teorija grafov, Steinerjev interval, razdalja, dobra premostljivost, mathematics, graph theory, Steiner interval, distance, well-bridgeness
Leto izida:2011
Št. strani:str. 1222-1235
Številčenje:Vol. 32, no. 8
UDK:519.17
COBISS_ID:16079193 Povezava se odpre v novem oknu
ISSN pri članku:0195-6698
NUK URN:URN:SI:UM:DK:JORLTX3K
Število ogledov:305
Število prenosov:19
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:European journal of combinatorics
Skrajšan naslov:Eur. j. comb.
Založnik:Academic Press
ISSN:0195-6698
COBISS.SI-ID:25427968 Novo okno

Sekundarni jezik

Jezik:Angleški jezik
Naslov:O lokalni 3-Steinerjevi konveksnosti
Opis:Given a graph ▫$G$▫ and a set of vertices ▫$W subset V(G)$▫, the Steiner interval of ▫$W$▫ is the set of vertices that lie on some Steiner tree with respect to ▫$W$▫. A set ▫$W subset V(G)$▫ is called ▫$g_3$▫-convex in ▫$G$▫, if the Steiner interval with respect to any three vertices from ▫$U$▫ lies entirely in ▫$U$▫. Henning et al. (2009) proved that if every ▫$j$▫-ball for all ▫$j ge 1$▫ is ▫$g_3$▫-convex in a graph ▫$G$▫, then ▫$G$▫ has no induced house nor twin ▫$C_4$▫, and every cycle in ▫$G$▫ of length at least six is well-bridged. In this paper we show that the converse of this theorem is true, thus characterizing the graphs in which all balls are ▫$g_3$▫-convex.


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